Graph-Theoretic Concepts in Computer Science
Preface
Program Committee
Table of Contents
Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces
1 Introduction
2 Reduction to Hypercubes
3 Farris-Fitch-Hartigan (FFH) Labeling
4 Examples
5 Median Hull Includes FFG Hull
6 FFH Hull Includes Median Hull
7 Conclusion
References
Data Management in Networks
Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs
1 Introduction
2 Definitions and Auxiliary Lemmas
3 EIP for the Cartesian Powers of H_{p,i}
4 Concluding Remarks
References
Approximate Constrained Bipartite Edge Coloring
1 Introduction
2 Bipartite Edge Coloring and Multicommodity Flows
3 Approximating the Multicommodity Flow Problem
4 Decreasing the Number of Colors
References
Maximum Clique Transversals
1 Introduction
2 Preliminaries
3 Fixed Parameter Results for Planar Graphs
3.1 Search-Tree Method
3.2 Reduction to a Problem Kernel
4 Approximations for Planar Graphs
5 Chordal Graphs of Diameter Two and k-Trees
6 Cographs and Graphs with Few P_4s
7 Comparability Graphs
8 Distance Hereditary Graphs
9 Conclusion
References
On the Tree-Degree of Graphs
1 Introduction
2 Preliminaries
3 Complete Separators in Edge-Intersection Graphs
4 Minimal Separators in Edge-Intersection Graphs
5 Treewidth
6 Complexity of Computing the Tree-Degree of a Graph
7 An Approach to Computing the Tree-Degrees for Some Classes of Graphs
References
On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms
1 Introduction
2 Reduction to Kernel by GE-Theorem
3 Efficient Search by DM-Decomposition
4 Putting All Together
5 Concluding Remarks
References
(k,+)-Distance-Hereditary Graphs
1 Introduction
2 Notation
3 Preliminary Results
4 Recognition Problem for ensuremath DH(k,+)
5 Studying Graphs in ensuremath DH(1,+)
6 Conclusions
References
On the Relationship between Clique-Width and Treewidth
1 Introduction
2 Notation and Definitions
3 Lower Bound
4 Upper Bound
5 Concluding Remarks
References
Planarity of the 2-Level Cactus Model
1 Introduction
2 Planarity of Trees with Additional Edges
3 The 2-Level Cactus Model
4 Planarity of the 2-Level Cactus
5 Final Remarks
References
Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach
1 Introduction
2 Preliminaries and the Algorithm
3 Distances in Graphs from the Weakly Chordal Hierarchy
3.1 Employing LexBFS--Orderings
3.2 Employing Lexical Orderings
4 Distances in Graphs with Small Size of Largest Induced Cycle: Employing BFS--Orderings
References
How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time
1 Introduction
2 Preliminaries
3 Examples
References
(g, f)-Factorizations Orthogonal to k Subgraphs
1 Introduction
2 Preliminaries
3 Factorization Orthogonal to k Edge Disjoint Sets
4 Some Extension to Factorization Orthogonal to k Vertex Disjoint Sets
References
On Star Coloring of Graphs
1 Introduction
2 Generalities
3 Trees, Cycles, Complete Bipartite Graphs, Hypercubes
4 d-Dimensional Grids
5 2-Dimensional Tori
6 Graphs with Bounded Treewidth
7 Conclusion
References
Graph Subcolorings: Complexity and Algorithms
1 Introduction and Results
2 The NP-Completeness of the Subcoloring Problem
2.1 Triangle-Free Graphs of Maximum Degree 4
2.2 Planar Graphs of Maximum Degree 4
2.3 The Hardness of k-Subcoloring for k >/_ 3
3 Graphs with Bounded Treewidth
4 Cographs
References
Approximation of Pathwidth of Outerplanar Graphs
1 Introduction
2 Definitions and Notations
3 Pathwidth of Outerplane Graphs
4 An Approximation Algorithm for Biconnected Outerplanar Graphs
5 Concluding Remarks
References
On the Monotonicity of Games Generated by Symmetric Submodular Functions
1 Introduction
2 A Min-max Theorem for Connectivity Functions
3 A General Framework for Conquest Games
4 Applications
4.1 Definitions
4.2 A Game for Cutwidth
4.3 Linear-Width and Search Games on Graphs
5 Conclusions
References
Multiple Hotlink Assignment
1 Introduction and Preliminaries
2 (k-1,k)-Hotlink Assignment
2.1 The Algorithm
2.2 Analysis of the Algorithm
3 (2,k)-Hotlink Assignment
4 (1,k)-Hotlink Assignment
5 Conclusions
5.1 Optimal Hotlink Length
5.2 Lower Bounds for Uniform Distribution
5.3 Summary of Results
References
Small k-Dominating Sets in Planar Graphs with Applications
1 Introduction
2 Plane Graphs
2.1 Preliminaries
2.2 Outerplanar Graphs
2.3 Planar Graphs
2.4 Main Result
2.5 Conjecture and Worst-Case
3 Treewidth and Chordality Bounded Graphs
4 Application to Compact Routing
References
Lower Bounds for Approximation Algorithms for the Steiner Tree Problem
1 Introduction
2 Notations and a General Framework for Greedy Algorithms
3 Relative Greedy Algorithm
4 Loss Contracting Algorithm
5 Iterated 1-Steiner Heuristic
6 Greedy-MSS
References
log n-Approximative NLCk-Decomposition in O(n2k+1) Time
1 Introduction
2 Basic Definitions
3 An Exact Algorithm
4 A Polynomial-Time Approximative Algorithm
4.1 Abstract Derivations
4.2 The Abstract Derivation Algorithm
4.3 Conclusion
References
On Subfamilies of AT-Free Graphs
1 Introduction
2 Background
3 Path Orderable Graphs and Strong Asteroid Free Graphs
4 Recognition of Path Orderable and Strong Asteroid Free Graphs
5 Concluding Remarks
References
Complexity of Coloring Graphs without Forbidden Induced Subgraphs
1 Preliminaries and Overview of Results
2 Polynomial Cases
3 Clique Covering of Sparse Graphs
4 NP--Complete Cases
5 Towards Two Forbidden Subgraphs
5.1 Types B versus C (Forests versus Forests)
5.2 Types A versus B (Cycles versus Claws)
5.3 Types A versus C (Cycles versus Linear Forests)
References
On Stable Cutsets in Line Graphs
1 Introduction
2 Decomposable Graphs Revisited
3 Stable Cutsets in Line Graphs
4 Observations
5 Stable Cutsets in Graphs with Maximum Degree 3
6 Stable Cutsets in Line Graphs of Maximum Degree 4
7 Concluding Remarks
References
On Strong Menger-Connectivity of Star Graphs
1 Introduction
2 Preliminaries
3 Bridging Paths from a Node to a Substar
4 The Strong Menger-Connectivity of Star Graphs
5 Conclusion
References
The Complexity of the Matching-Cut Problem
1 Introduction
2 Preliminaries
3 NP-Completeness of the Matching-Cut Problem
4 Simple Graphs and Graphs with Maximum Degree Four
5 Matching-Cuts of Series-Parallel Graphs
6 Conclusions and Open Problems
References
De Bruijn Graphs and DNA Graphs
1 Introduction
2 Preliminaries
3 The Problem Variant with a Fixed Label Length
4 The Problem Variant with a Fixed Alphabet Size
References
A Generic Greedy Algorithm, Partially-Ordered Graphs and NP-Completeness
1 Introduction
2 Basic Definitions
3 Our Results
References
Critical and Anticritical Edges in Perfect Graphs
1 Introduction
2 Critical and Anticritical Edges
3 Which Graph Classes Admit Critical or Anticritical Edges?
4 Perfect and Co-perfect Edge Orders
References
Author Index