Accepted Papers

The following papers have been accepted by the program committee of WG 2004. The ordered appearance in the program will be available within the next days.

Boris Goldengorin, Marcel Turkensteen:What is the best branching rule for the ATSP?
Shin-ichi Nakano, Takeaki Uno:Constant Time Generation of Trees with Specified Diameter
Zhi-Zhong Chen, Tatsuie Tsukiji:Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
Franz Baader:A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept
Tim Nieberg, Johann Hurink, Walter Kern:A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs
Hans Bodlaender, Arie Koster:On the Maximum Cardinality Search Lower Bound for Treewidth
Jiri Fiala, Peter Golovach, Jan Kratochvil:Elegant distance constrained labelings of trees
Jayme Szwarcfiter, Mitre C Dourado, Fabio Protti:Characterization and recognition of generalized clique-Helly graphs
Guido Proietti, Michele Conforti, Anna Galluccio:Edge-connectivity augmentation and network matrices
Gabriele Di Stefano, Sabine Cornelsen:Treelike Graphs:Characterization, Recognition, and Applications
Jerome Monnot, Dominique de Werra, Marc Demange, Vangelis Th. Paschos:The hypocoloring problem:complexity and approximability results when the chromatic number is small
Md. Saidur Rahman, Kazuyuki Miura, Takao Nishizeki:Octagonal Drawings of Plane Graphs with Prescribed Face Areas
Michaël Rao:Coloring a graph using split decomposition
Yoshio Okamoto, Thomas Bietenhader:Core Stability of Minimum Coloring Games
Stavros Nikolopoulos, Leonidas Palios:Recognizing HHD-free and Welsh-Powell Opposition Graphs
Fabrizio Grandoni, Giuseppe F. Italiano:Decremental Clique Problem
Feodor F. Dragan, Chenyu Yan, Derek G. Corneil:Collective Tree Spanners and Routing in AT-free Related Graphs (Extended Abstract)
Mordecai Golin, Yiu Cho Leung:Unhooking Circulant Graphs
Christian Sloper, Mike Fellows, Pinar Heggernes, Frances Rosamond, Jan Arne Telle:Exact Algorithms for finding k disjoint triangles in an arbitrary graph
Takehiro Ito, Xiao Zhou, Takao Nishizeki:Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size
Massimiliano Caramia, Nicola Apollonio, Giuseppe F. Italiano:A Stochastic Location Problem with Applications to Tele-Diagnostic
Christophe Paul, Christophe Crespelle:Fully-dynamic recognition algorithm and certificate for directed cographs
Cyril Gavoille, Bonichon N., Hanusse N., Poulalhon D., Schaeffer G.:Planar Graphs, via Well-Orderly Maps and Trees
Daniel Sawitzki:A Symbolic Approach to the All-Pairs Shortest-Paths Problem
Fedor Fomin, Dieter Kratsch, Gerhard Woeginger:Exact (exponential) algorithms for the dominating set problem
Daniel Paulusma, H.J. Broersma, G.J.M. Smit, F. Vlaardingerbroek, G.J. Woeginger:The computational complexity of the minimum weight processor assignment problem
Valentin Brimkov, Reneta Barneva, Reinhard Klette, Joseph Straight:Lovasz theta-function of a class of graphs representing digital lines
Fabien de Montgolfier, Jean-Luc Fouquet, Michel Habib, Jean-Marie Vanherpe:Bimodular decomposition of bipartite graphs
David Juedes, Benny Chor, Mike Fellows:Linear Kernels in Linear Time, or How to Save k Colors in O(n^2) steps
Eduardo Moreno, Martin Matamala:Minimal de Bruijn Sequence in a Language with Forbidden Substrings
Michael Baur, Ulrik Brandes:Crossing Reduction in Circular Layouts