Combinatorial Algorithms

1. Front Matter

   PDF

2. Invited Talks

   1. Branching Systems

      • Jack Edmonds

      Pages 1-1

   2. Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology

      • Michael Fellows

      Pages 2-10

   3. Succinct Representations of Trees

      • Giovanni Manzini

      Pages 11-18

   4. K _t Minors in Large t-Connected Graphs

      • Robin Thomas

      Pages 19-19

   5. Intractability in Graph Drawing and Geometry: FPT Approaches

      • Sue Whitesides

      Pages 20-23

3. Contributed Talks

   1. Evaluation of Recoverable-Robust Timetables on Tree Networks

      • Gianlorenzo D’Angelo, Gabriele Di Stefano, Alfredo Navarra

      Pages 24-35

   2. Weighted LCS

      • Amihood Amir, Zvi Gotthilf, B. Riva Shalom

      Pages 36-47

   3. Integrality Properties of Certain Special Balanceable Families

      • Nicola Apollonio, Massimiliano Caramia

      Pages 48-59

   4. Forbidden Subgraph Colorings and the Oriented Chromatic Number

      • N. R. Aravind, C. R. Subramanian

      Pages 60-71

   5. Polynomial Kernels for 3-Leaf Power Graph Modification Problems

      • Stéphane Bessy, Christophe Paul, Anthony Perez

      Pages 72-82

   6. Approximating the Max Edge-Coloring Problem

      • Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

      Pages 83-94

   7. Three Complexity Results on Coloring P _k -Free Graphs

      • Hajo Broersma, Fedor V. Fomin, Petr A. Golovach, Daniël Paulusma

      Pages 95-104

   8. Fully Decomposable Split Graphs

      • Hajo Broersma, Dieter Kratsch, Gerhard J. Woeginger

      Pages 105-112

   9. Feedback Vertex Set on Graphs of Low Cliquewidth

      • Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle

      Pages 113-124

   10. Note on Decomposition of K _n,n into (0,j)-prisms

       • Sylwia Cichacz, Dalibor Fronček, Petr Kovář

       Pages 125-133

   11. Edge-Simple Circuits through 10 Ordered Vertices in Square Grids

       • David Coudert, Frédéric Giroire, Ignasi Sau

       Pages 134-145

   12. Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search

       • Christophe Crespelle, Philippe Gambette

       Pages 146-157

   13. LPF Computation Revisited

       • Maxime Crochemore, Lucian Ilie, Costas S. Iliopoulos, Marcin Kubica, Wojciech Rytter, Tomasz Waleń

       Pages 158-169

   14. Limiting Distribution for Distances in k-Trees

       • Alexis Darrasse, Michèle Soria

       Pages 170-182

This book constitutes the revised selected papers of the 20th International Workshop on Combinatorial Algorithms, held in June/July 2009 in the castle of Hradec nad Moravicí, Czech Republic. The 41 papers included in this volume together with 5 invited papers were carefully reviewed and selected from over 100 submissions. The topics dealt with are algorithms and data structures, applications, combinatorial enumeration, combinatorial optimization, complexity theory, computational biology, databases, decompositions and combinatorial designs, discrete and computational geometry, including graph drawing, and graph theory and combinatorics.

• Graph
• Graph theory
• algorithms
• combinatorial optimization
• combinatorics
• complexity
• computational geometry
• data structures
• databases
• algorithm analysis and problem complexity

• Institute for Theoretical Computer Science and Department of Applied Mathematics, Charles University, Prague, Czech Republic

  Jiří Fiala, Jan Kratochvíl

• School of Electrical Engineering and Computer Science, The University of Newcastle, Callaghan, Australia

  Mirka Miller

Policies and ethics