Graph-theoretic concepts in computer science : 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 : revised papers / Petr Kolman, Jan Kratochvíl (eds.)
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 BoundsConclusion; 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-setsA 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 GraphConclusions; 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_4NP-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
Summary
Annotation This text constitutes the revised selected papers of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, held in the Czech Republic, in June 2011. The 28 revised papers presented were carefully reviewed and selected from 52 submissions
