Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001 Boltenhagen, Germany, June 14-16, 2001 Proceedings (Lecture Notes in Computer Science)

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. Median Hulls As Steiner Hulls In Rectilinear And Molecular Sequence Spaces -- Data Management In Networks -- Edge-isoperimetric Problems For Cartesian Powers Of Regular Graphs -- Approximate Constrained Bipartite Edge Coloring -- Maximum Clique Transversals -- On The Tree-degree Of Graphs -- On Constrained Minimum Vertex Covers Of Bipartite Graphs: Improved Algorithms -- (k+) -disatance- Herediatry Graphs -- On The Relationship Between Clique-width And Treewidth -- Planarity Of The 2-level Cactus Model -- Estimating All Pairs Shortest Paths In Restricted Graph Families: A Unified Approach -- How To Solve Np-hard Graph Problems On Clique-width Bounded Graphs In Polynomial Time -- (g, F)-factorizations Orthogonal To K Subgraphs -- On Star Coloring Of Graphs -- Graph Subcolorings: Complexity And Algorithms -- Approximation Of Pathwidth Of Outerplanar Graphs -- On The Monotonicity Of Games Generated By Symmetric Submodular Functions -- Multiple Hotlink Assignment -- Small K-dominating Sets In Planar Graphs With Applications -- Lower Bounds For Algorithms For The Steiner Tree Problem -- Log N-approximative Nlck-decomposition In O(n 2k+1) Time -- On Subfamilies Of At-free Graphs -- Complexity Of Coloring Graphs Without Forbidden Induced Subgraphs -- On Stable Cutsets In Line Graphs -- On Strong Menger-connectivity Of Star Graphs -- The Complexity Of The Matching-cut Problem -- De Bruijn Graphs And Dna Graphs -- A Generic Greedy Algorithm, Partially-ordered Graphs And Np-completeness -- Critical And Anticritical Edges In Perfect Graphs. Andreas Brandstädt, Van Bang Le (eds.). Includes Bibliographical References And Index. 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 Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings Author: Andreas Brandstädt, Van Bang Le Published by Springer Berlin Heidelberg ISBN: 978-3-540-42707-0 DOI: 10.1007/3-540-45477-2 Table of Contents: Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces Data Management in Networks Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs Approximate Constrained Bipartite Edge Coloring Maximum Clique Transversals On the Tree-Degree of Graphs On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms (k+) -Disatance- Herediatry Graphs On the Relationship between Clique-Width and Treewidth Planarity of the 2-Level Cactus Model Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time (g, f)-Factorizations Orthogonal to k Subgraphs On Star Coloring of Graphs Graph Subcolorings: Complexity and Algorithms Approximation of Pathwidth of Outerplanar Graphs On the Monotonicity of Games Generated by Symmetric Submodular Functions Multiple Hotlink Assignment Small k-Dominating Sets in Planar Graphs with Applications Lower Bounds for Algorithms for the Steiner Tree Problem This book constitutes the thoroughly refereed proceedings of the 39th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2013, held in Lübeck, Germany, in June 2013. The 34 revised full papers presented were carefully reviewed and selected from 61 submissions. The book also includes two abstracts. The papers cover a wide range of topics in graph theory related to computer science, such as structural graph theory with algorithmic or complexity applications; design and analysis of sequential, parallel, randomized, parameterized and distributed graph and network algorithms; computational complexity of graph and network problems; computational geometry; graph grammars, graph rewriting systems and graph modeling; graph drawing and layouts; random graphs and models of the web and scale-free networks; and support of these concepts by suitable implementations and applications. This text of the refereed post-workshop proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, provides a wealth of contemporary results for various classes of graphs, graph computations, graph algorithms and graph-theoretical applications in various fields.