30. WG 2004: Bad Honnef, Germany
Juraj Hromkovic, Manfred Nagl, Bernhard Westfechtel (Eds.): Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers. Springer 2004 Lecture Notes in Computer Science ISBN 3-540-24132-9
Invited Papers
- Derek G. Corneil: Lexicographic Breadth First Search - A Survey. 1-19
- Roger Wattenhofer: Wireless Networking: Graph Theory Unplugged. 20-32
Graph Algorithms: Trees
- Sabine Cornelsen, Gabriele Di Stefano: Treelike Comparability Graphs: Characterization, Recognition, and Applications. 46-57
- Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Elegant Distance Constrained Labelings of Trees. 58-67
- Feodor F. Dragan, Chenyu Yan, Derek G. Corneil: Collective Tree Spanners and Routing in AT-free Related Graphs. 68-80
Graph Algorithms: Recognition and Decomposition
- Hans L. Bodlaender, Arie M. C. A. Koster: On the Maximum Cardinality Search Lower Bound for Treewidth. 81-92
- Christophe Crespelle, Christophe Paul: Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs. 93-104
- Stavros D. Nikolopoulos, Leonidas Palios: Recognizing HHD-free and Welsh-Powell Opposition Graphs. 105-116
- Jean-Luc Fouquet, Michel Habib, Fabien de Montgolfier, Jean-Marie Vanherpe: Bimodular Decomposition of Bipartite Graphs. 117-128
- Michaël Rao: Coloring a Graph Using Split Decomposition. 129-141
Graph Algorithms: Various Problems
- Daniel Sawitzki: A Symbolic Approach to the All-Pairs Shortest-Paths Problem. 154-167
- Eduardo Moreno, Martín Matamala: Minimal de Bruijn Sequence in a Language with Forbidden Substrings. 168-176
- Franz Baader: A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL. 177-188
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
- Nicola Apollonio, Massimiliano Caramia, Giuseppe F. Italiano: A Stochastic Location Problem with Applications to Tele-diagnostic. 201-213
- Tim Nieberg, Johann Hurink, Walter Kern: A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. 214-221
- Boris Goldengorin, Gerard Sierksma, Marcel Turkensteen: Tolerance Based Algorithms for the ATSP. 222-234
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
- Fedor V. Fomin, Dieter Kratsch, Gerhard J. Woeginger: Exact (Exponential) Algorithms for the Dominating Set Problem. 245-256
Counting, Combinatorics, and Optimization
- Benny Chor, Mike Fellows, David W. Juedes: Linear Kernels in Linear Time, or How to Save k Colors in O(n2) Steps. 257-269
- Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, Gilles Schaeffer: Planar Graphs, via Well-Orderly Maps and Trees. 270-284
- 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
- Mordecai J. Golin, Yiu-Cho Leung: Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters. 296-307
Applications (Biology, Graph Drawing)
- Zhi-Zhong Chen, Tatsuie Tsukiji: Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs. 308-319
- Md. Saidur Rahman, Kazuyuki Miura, Takao Nishizeki: Octagonal Drawings of Plane Graphs with Prescribed Face Areas. 320-331
Graph Classes and NP Hardness
- Mitre Costa Dourado, Fábio Protti, Jayme Luiz Szwarcfiter: Characterization and Recognition of Generalized Clique-Helly Graphs. 344-354
- Michele Conforti, Anna Galluccio, Guido Proietti: Edge-Connectivity Augmentation and Network Matrices. 355-364
- Takehiro Ito, Xiao Zhou, Takao Nishizeki: Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size. 365-376
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T203413 by the dblp team