Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers

✍ Scribed by Alberto Marchetti-Spaccamela (auth.), Petr Kolman, Jan Kratochvíl (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2011
• Tongue: English
• Leaves: 357
• Series: Lecture Notes in Computer Science 6986
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Front Matter....Pages -
Structures and Hyperstructures in Metabolic Networks....Pages 1-4
Important Separators and Parameterized Algorithms....Pages 5-10
Split Clique Graph Complexity....Pages 11-22
On Searching for Small Kochen-Specker Vector Systems....Pages 23-34
Characterizations of Deque and Queue Graphs....Pages 35-46
Graph Classes with Structured Neighborhoods and Algorithmic Applications....Pages 47-58
Exact Algorithms for Kayles....Pages 59-70
The Cinderella Game on Holes and Anti-holes....Pages 71-82
On the Complexity of Planar Covering of Small Graphs....Pages 83-94
Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses....Pages 95-106
Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs....Pages 107-118
List Coloring in the Absence of a Linear Forest....Pages 119-130
Parameterized Complexity of Eulerian Deletion Problems....Pages 131-142
Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons....Pages 143-154
Maximum Independent Set in 2-Direction Outersegment Graphs....Pages 155-166
Complexity of Splits Reconstruction for Low-Degree Trees....Pages 167-178
Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem....Pages 179-190
Alternation Graphs....Pages 191-202
Improved Bounds for Minimum Fault-Tolerant Gossip Graphs....Pages 203-214
Parameterized Two-Player Nash Equilibrium....Pages 215-226
Counting Independent Sets in Claw-Free Graphs....Pages 227-237
On the Independence Number of Graphs with Maximum Degree 3....Pages 238-249
On Computing an Optimal Semi-matching....Pages 250-261
Planar k -Path in Subexponential Time and Polynomial Space....Pages 262-270
Approximability of the Path-Distance-Width for AT-free Graphs....Pages 271-282
Hanani-Tutte and Monotone Drawings....Pages 283-294
On Collinear Sets in Straight-Line Drawings....Pages 295-306
From Few Components to an Eulerian Graph by Adding Arcs....Pages 307-318
Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid....Pages 319-330
A Polynomial Time Algorithm for Bounded Directed Pathwidth....Pages 331-342
Back Matter....Pages -

✦ Subjects

Discrete Mathematics in Computer Science; Algorithm Analysis and Problem Complexity; Geometry; Algorithms; Computer Communication Networks; Data Structures