Graph-Theoretic Concepts in Computer Science

1. Front Matter

   PDF

2. Structures and Hyperstructures in Metabolic Networks

   • Alberto Marchetti-Spaccamela

   Pages 1-4

3. Important Separators and Parameterized Algorithms

   • Dániel Marx

   Pages 5-10

4. Split Clique Graph Complexity

   • Liliana Alcón, Luerbio Faria, Celina M. H. de Figueiredo, Marisa Gutierrez

   Pages 11-22

5. On Searching for Small Kochen-Specker Vector Systems

   • Felix Arends, Joël Ouaknine, Charles W. Wampler

   Pages 23-34

6. Characterizations of Deque and Queue Graphs

   • Christopher Auer, Andreas Gleißner

   Pages 35-46

7. Graph Classes with Structured Neighborhoods and Algorithmic Applications

   • Rémy Belmonte, Martin Vatshelle

   Pages 47-58

8. Exact Algorithms for Kayles

   • Hans L. Bodlaender, Dieter Kratsch

   Pages 59-70

9. The Cinderella Game on Holes and Anti-holes

   • Marijke H. L. Bodlaender, Cor A. J. Hurkens, Gerhard J. Woeginger

   Pages 71-82

10. On the Complexity of Planar Covering of Small Graphs

    • Ondřej Bílka, Jozef Jirásek, Pavel Klavík, Martin Tancer, Jan Volec

    Pages 83-94

11. Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses

    • Katarína Cechlárová, Eva Jelínková

    Pages 95-106

12. Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs

    • Christine Cheng, Eric McDermid, Ichiro Suzuki

    Pages 107-118

13. List Coloring in the Absence of a Linear Forest

    • Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma

    Pages 119-130

14. Parameterized Complexity of Eulerian Deletion Problems

    • Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Ildikó Schlotter

    Pages 131-142

15. Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons

    • Andreas Emil Feldmann, Shantanu Das, Peter Widmayer

    Pages 143-154

16. Maximum Independent Set in 2-Direction Outersegment Graphs

    • Holger Flier, Matúš Mihalák, Peter Widmayer, Anna Zych

    Pages 155-166

17. Complexity of Splits Reconstruction for Low-Degree Trees

    • Serge Gaspers, Mathieu Liedloff, Maya Stein, Karol Suchan

    Pages 167-178

18. Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem

    • Andrew R. A. McGrae, Michele Zito

    Pages 179-190

19. Alternation Graphs

    • Magnús M. Halldórsson, Sergey Kitaev, Artem Pyatkin

    Pages 191-202

20. Improved Bounds for Minimum Fault-Tolerant Gossip Graphs

    • Toru Hasunuma, Hiroshi Nagamochi

    Pages 203-214

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.

• NP-completeness
• combinatorial game
• parameterized complexity
• split graphs
• topological graph
• algorithm analysis and problem complexity
• data structures

• KAM MFF UK, Charles University, Praha 1, Czech Republic

  Petr Kolman, Jan Kratochvíl

Policies and ethics