Graph-Theoretic Concepts in Computer Science
37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011, Revised Papers
Published on 1. December 2011
XI, 344 pages
978-3-642-25870-1 (ISBN)
Description
This book constitutes the revised selected papers of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, held at Teplá Monastery, Czech Republic, in June 2011.
The 28 revised papers presented were carefully reviewed and selected from 52 submissions. The workshop aims at merging theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, and by extracting new graph theoretic problems from applications.
More details
Other editions
Additional editions
Petr Kolman | Jan Kratochvíl
Graph-Theoretic Concepts in Computer Science
37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011, Revised Papers
Book
12/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Intro
- Title page
- Preface
- Organization
- Table of Contents
- Structures and Hyperstructures in Metabolic Networks
- Introduction
- Structural Characterization
- Dynamic Characterization
- References
- Important Separators and Parameterized Algorithms
- Introduction
- Multiway Cut
- Directed Graphs
- Conclusions
- References
- Split Clique Graph Complexity
- Introduction
- NP-Complete Split Clique Graph Classes
- Polynomially Solvable Split Clique Graph Classes
- Open Related Problems
- References
- On Searching for Small Kochen-Specker Vector Systems
- Introduction
- Kochen-Specker Vector Systems
- Embeddability
- Lower Bounds
- Conclusion
- References
- Characterizations of Deque and Queue Graphs
- Introduction
- Preliminaries
- Deque Graphs
- Characterizing Deque Graphs
- Hamiltonian Paths in Deque and Queue Graphs
- Deciding If a Graph Is a Deque Graph Is NP-Complete
- Queue Graphs
- Conclusion
- References
- Graph Classes with Structured Neighborhoods and Algorithmic Applications
- Introduction
- Framework
- Upper Bounds on Boolean-Width of Graph Classes
- Vertex Partitioning Problems
- Lower Bounds
- Conclusion
- References
- Exact Algorithms for Kayles
- Introduction
- Preliminaries
- An Upper Bound on the Number of K-sets
- A Bound on the Number of K-sets in Trees
- The Exact Algorithm
- Lower Bounds
- Conclusions
- References
- The Cinderella Game on Holes and Anti-holes
- Introduction
- Definitions and First Results
- The Game on General Graphs
- The Game on Holes
- Proof of the Upper Bound for GREEDY
- Proof of the Lower Bound for GREEDY
- The Game on Anti-holes
- Conclusions and Conjectures
- References
- On the Complexity of Planar Covering of Small Graphs
- Introduction
- Hardness of Planar Covering of $K_6$
- Hardness of Planar Covering of $K_4, K_5, K_4+$ and $K_5-$
- Hardness of Planar Covering of the Dumbbell Graph
- Conclusions
- References
- Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses
- Introduction
- Preliminaries
- Bounds for sat(M)
- Inapproximability
- The Transformation
- Inapproximability for Max-SHDTri
- Inapproximability for Max-SHDTies
- Conclusion and Open Problems
- References
- Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
- Introduction
- Preliminaries and Definitions
- Simplifying the Graph
- Finding Large Planar Subgraphs
- Induced Planar Subgraphs
- Planar Subgraphs
- Acyclic Colorings
- Acyclically Coloring $GR=K_4$
- NP-Hardness for $d = 4$
- References
- List Coloring in the Absence of a Linear Forest
- Introduction
- A Generic Approach for Coloring H-Free Graphs
- Coloring $(rP1+P5)$-Free Graphs
- Parameterized Complexity Results
- Future Work
- References
- Parameterized Complexity of Eulerian Deletion Problems
- Introduction
- Notation and Preliminaries
- Polynomial-Time Solvable Cases
- Eulerian Edge-Deletion Problems
- FPT Algorithms
- Non-existence of a Polynomial Kernel for Undirected and Directed Eulerian Edge Deletion
- Node-Deletion Problems
- Conclusion
- References
- Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons
- Comparing Optimal with Restricted Cuts
- Cuts in Polygons
- Removing Rectangular Lines
- Removing Staircase Lines
- Converting Lines in Polygons to Segments in Grids
- References
- Maximum Independent Set in 2-Direction Outersegment Graphs
- Introduction
- Solving the Tripartite MIS-2-Dir-Outer-SEG
- Structure of an Optimal Solution
- Algorithm for Tripartite MIS-2-Dir-Outer-SEG
- Decomposing MIS-2-Dir-Outer-SEG
- References
- Complexity of Splits Reconstruction for Low-Degree Trees
- Introduction
- WSR2is Strongly NP-Complete
- Algorithm for WSR2 with Few Distinct Vertex Weights
- SR3is NP-Complete
- Freely Choosable Weights
- Conclusion
- References
- Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
- Introduction
- Algorithms
- A Useful Reduction
- Forests of Paths
- Trees
- General Planar Graphs
- References
- Alternation Graphs
- Introduction
- Definitions, Notation, and Known Results
- Characterization of Alternation Graphs by Orientability
- The Alternation Number of Graphs
- Characteristics of Alternation Graphs
- Concluding Remarks and Open Questions
- References
- Improved Bounds for Minimum Fault-Tolerant Gossip Graphs
- Introduction
- Construction of Fault-Tolerant Gossip Graphs
- Fault-Tolerant Gossip Graphs Based on Hypercubes
- Fault-Tolerant Gossip Graphs Based on Circulant Graphs
- A Lower Bound
- References
- Parameterized Two-Player Nash Equilibrium
- Introduction
- Preliminaries
- Sparse Games
- Non-negative Payoffs
- No Polynomial Kernels
- Locally Bounded Treewidth Games
- Unbalanced Games
- Conclusions
- References
- Counting Independent Sets in Claw-Free Graphs
- Introduction
- Preliminaries
- Procedures
- FOLDING
- REDUCTION
- BRANCHING
- Algorithm TCOUNT3
- Algorithm TCOUNT6
- Algorithm TCOUNT
- References
- On the Independence Number of Graphs with Maximum Degree 3
- Introduction
- Preliminaries
- Structural Results
- A Combinatorial Result
- The First Phase
- The Second Phase
- The Third Phase
- The Kernel
- References
- On Computing an Optimal Semi-matching
- Introduction
- Preliminaries
- Balancing Subroutine
- Dividing Subroutine
- The Main Algorithm
- Conclusion
- References
- Planar k-Path in Subexponential Time and Polynomial Space
- Introduction
- Definitions and Notations
- Polynomial Space Algorithm for the k-Path Problem
- Conclusion and Discussion
- References
- Approximability of the Path-Distance-Width for AT-free Graphs
- Introduction
- Preliminaries
- NP-Hardness for Cobipartite Graphs
- Approximating the Path-Distance-Width
- Approximating the Path-Distance-Width for k-Cocomparability Graphs
- Approximating the Path-Distance-Width for AT-free Graphs
- Approximating the Path-Distance-Width for Proper Interval Graphs
- A Polynomial-Time Solvable Case
- Concluding Remarks
- References
- Hanani-Tutte and Monotone Drawings
- Introduction
- Weak Hanani-Tutte for Monotone Drawings
- Strong Hanani-Tutte for Monotone Drawings
- Monotone Crossing Numbers
- Open Questions
- References
- On Collinear Sets in Straight-Line Drawings
- Introduction
- Basic Definitions
- Known Results on the Untangling Problem
- Known Results on the Allocation Problem
- Our Present Contribution
- Preliminaries
- Graphs with Small Collinear Sets
- Graphs with Large Free Collinear Sets
- Further Questions
- References
- From Few Components to an Eulerian Graph by Adding Arcs
- Introduction
- Limiting Imbalance Helps
- Generating Advice for Eulerian Extension
- Solving Eulerian Extension with Advice
- Non-existence of Polynomial-Size Problem Kernels
- Conclusion
- References
- Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
- Introduction
- Chordal B0-VPG Graphs
- Algorithm
- 2-RowB0-VPG Graphs
- LL-Drawings
- PQ-Trees
- Algorithm
- Conclusion
- References
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Introduction
- Preliminaries
- Search Tree Pruning
- Proof of the Commitment Lemma
- Implementation Details
- Concluding Remarks
- References
- Author Index
