30. WG 2004: Bad Honnef, Germany

Invited Papers

• Derek G. Corneil:
  Lexicographic Breadth First Search - A Survey. 1-19
  Electronic Edition (link) BibTeX
• Roger Wattenhofer:
  Wireless Networking: Graph Theory Unplugged. 20-32
  Electronic Edition (link) BibTeX

Graph Algorithms: Trees

• Shin-Ichi Nakano, Takeaki Uno:
  Constant Time Generation of Trees with Specified Diameter. 33-45
  Electronic Edition (link) BibTeX
• Sabine Cornelsen, Gabriele Di Stefano:
  Treelike Comparability Graphs: Characterization, Recognition, and Applications. 46-57
  Electronic Edition (link) BibTeX
• Jirí Fiala, Petr A. Golovach, Jan Kratochvíl:
  Elegant Distance Constrained Labelings of Trees. 58-67
  Electronic Edition (link) BibTeX
• Feodor F. Dragan, Chenyu Yan, Derek G. Corneil:
  Collective Tree Spanners and Routing in AT-free Related Graphs. 68-80
  Electronic Edition (link) BibTeX

Graph Algorithms: Recognition and Decomposition

• Hans L. Bodlaender, Arie M. C. A. Koster:
  On the Maximum Cardinality Search Lower Bound for Treewidth. 81-92
  Electronic Edition (link) BibTeX
• Christophe Crespelle, Christophe Paul:
  Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs. 93-104
  Electronic Edition (link) BibTeX
• Stavros D. Nikolopoulos, Leonidas Palios:
  Recognizing HHD-free and Welsh-Powell Opposition Graphs. 105-116
  Electronic Edition (link) BibTeX
• Jean-Luc Fouquet, Michel Habib, Fabien de Montgolfier, Jean-Marie Vanherpe:
  Bimodular Decomposition of Bipartite Graphs. 117-128
  Electronic Edition (link) BibTeX
• Michaël Rao:
  Coloring a Graph Using Split Decomposition. 129-141
  Electronic Edition (link) BibTeX

Graph Algorithms: Various Problems

• Fabrizio Grandoni, Giuseppe F. Italiano:
  Decremental Clique Problem. 142-153
  Electronic Edition (link) BibTeX
• Daniel Sawitzki:
  A Symbolic Approach to the All-Pairs Shortest-Paths Problem. 154-167
  Electronic Edition (link) BibTeX
• Eduardo Moreno, Martín Matamala:
  Minimal de Bruijn Sequence in a Language with Forbidden Substrings. 168-176
  Electronic Edition (link) BibTeX
• Franz Baader:
  A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL. 177-188
  Electronic Edition (link) BibTeX

Optimization and Approximation Algorithms

• Hajo Broersma, Daniël Paulusma, Gerard J. M. Smit, Frank Vlaardingerbroek, Gerhard J. Woeginger:
  The Computational Complexity of the Minimum Weight Processor Assignment Problem. 189-200
  Electronic Edition (link) BibTeX
• Nicola Apollonio, Massimiliano Caramia, Giuseppe F. Italiano:
  A Stochastic Location Problem with Applications to Tele-diagnostic. 201-213
  Electronic Edition (link) BibTeX
• Tim Nieberg, Johann Hurink, Walter Kern:
  A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. 214-221
  Electronic Edition (link) BibTeX
• Boris Goldengorin, Gerard Sierksma, Marcel Turkensteen:
  Tolerance Based Algorithms for the ATSP. 222-234
  Electronic Edition (link) BibTeX

Parameterized Complexity and Exponential Algorithms

• Mike Fellows, Pinar Heggernes, Frances A. Rosamond, Christian Sloper, Jan Arne Telle:
  Finding k Disjoint Triangles in an Arbitrary Graph. 235-244
  Electronic Edition (link) BibTeX
• Fedor V. Fomin, Dieter Kratsch, Gerhard J. Woeginger:
  Exact (Exponential) Algorithms for the Dominating Set Problem. 245-256
  Electronic Edition (link) BibTeX

Counting, Combinatorics, and Optimization

• Benny Chor, Mike Fellows, David W. Juedes:
  Linear Kernels in Linear Time, or How to Save k Colors in O(n²) Steps. 257-269
  Electronic Edition (link) BibTeX
• Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, Gilles Schaeffer:
  Planar Graphs, via Well-Orderly Maps and Trees. 270-284
  Electronic Edition (link) BibTeX
• Valentin E. Brimkov, Reneta P. Barneva, Reinhard Klette, Joseph Straight:
  Efficient Computation of the Lovász Theta Function for a Class of Circulant Graphs. 285-295
  Electronic Edition (link) BibTeX
• Mordecai J. Golin, Yiu-Cho Leung:
  Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters. 296-307
  Electronic Edition (link) BibTeX

Applications (Biology, Graph Drawing)

• Zhi-Zhong Chen, Tatsuie Tsukiji:
  Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs. 308-319
  Electronic Edition (link) BibTeX
• Md. Saidur Rahman, Kazuyuki Miura, Takao Nishizeki:
  Octagonal Drawings of Plane Graphs with Prescribed Face Areas. 320-331
  Electronic Edition (link) BibTeX
• Michael Baur, Ulrik Brandes:
  Crossing Reduction in Circular Layouts. 332-343
  Electronic Edition (link) BibTeX

Graph Classes and NP Hardness

• Mitre Costa Dourado, Fábio Protti, Jayme Luiz Szwarcfiter:
  Characterization and Recognition of Generalized Clique-Helly Graphs. 344-354
  Electronic Edition (link) BibTeX
• Michele Conforti, Anna Galluccio, Guido Proietti:
  Edge-Connectivity Augmentation and Network Matrices. 355-364
  Electronic Edition (link) BibTeX
• Takehiro Ito, Xiao Zhou, Takao Nishizeki:
  Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size. 365-376
  Electronic Edition (link) BibTeX
• Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos:
  The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small. 377-388
  Electronic Edition (link) BibTeX
• Thomas Bietenhader, Yoshio Okamoto:
  Core Stability of Minimum Coloring Games. 389-401
  Electronic Edition (link) BibTeX