Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings

Hans-J. Bandelt (auth.), Andreas Brandstädt, Van Bang Le (eds.)3540427074, 9783540427070

This book constitutes the thoroughly refereed post-workshop proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001, held in Boltenhagen, Germany, in June 2001.
The 27 revised full papers presented together with two invited contributions were carefully reviewed and selected from numerous submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms and graph-theoretical applications in various fields.

---

Table of contents :
Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces….Pages 1-7
Data Management in Networks….Pages 8-8
Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs….Pages 9-20
Approximate Constrained Bipartite Edge Coloring….Pages 21-31
Maximum Clique Transversals….Pages 32-43
On the Tree-Degree of Graphs….Pages 44-54
On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms….Pages 55-65
( k +) -Disatance- Herediatry Graphs….Pages 66-77
On the Relationship between Clique-Width and Treewidth….Pages 78-90
Planarity of the 2-Level Cactus Model….Pages 91-102
Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach….Pages 103-116
How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time….Pages 117-128
( g, f )-Factorizations Orthogonal to k Subgraphs….Pages 129-139
On Star Coloring of Graphs….Pages 140-153
Graph Subcolorings: Complexity and Algorithms….Pages 154-165
Approximation of Pathwidth of Outerplanar Graphs….Pages 166-176
On the Monotonicity of Games Generated by Symmetric Submodular Functions….Pages 177-188
Multiple Hotlink Assignment….Pages 189-200
Small k -Dominating Sets in Planar Graphs with Applications….Pages 201-216
Lower Bounds for Algorithms for the Steiner Tree Problem….Pages 217-228
log n -Approximative NLC k -Decomposition in O ( n 2k+1 ) Time….Pages 229-240
On Subfamilies of AT-Free Graphs….Pages 241-253
Complexity of Coloring Graphs without Forbidden Induced Subgraphs….Pages 254-262
On Stable Cutsets in Line Graphs….Pages 263-271
On Strong Menger-Connectivity of Star Graphs….Pages 272-283
The Complexity of the Matching-Cut Problem….Pages 284-295
De Bruijn Graphs and DNA Graphs….Pages 296-305
A Generic Greedy Algorithm, Partially-Ordered Graphs and NP-Completeness….Pages 306-316
Critical and Anticritical Edges in Perfect Graphs….Pages 317-327