Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers

✍ Scribed by David Eppstein (auth.), Christophe Paul, Michel Habib (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2010
• Tongue: English
• Leaves: 364
• Series: Lecture Notes in Computer Science 5911 : Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed post-conference proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009, held in Montpellier, France, in June 2009.

The 28 revised full papers presented together with two invited papers were carefully reviewed and selected from 69 submissions. The papers feature original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, diagram methods, and support of these concepts by suitable implementations.

✦ Table of Contents

Front Matter....Pages -
Graph-Theoretic Solutions to Computational Geometry Problems....Pages 1-16
Algorithms for Classes of Graphs with Bounded Expansion....Pages 17-32
A Graph Polynomial Arising from Community Structure (Extended Abstract)....Pages 33-43
Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs....Pages 44-53
Maximum Series-Parallel Subgraph....Pages 54-65
Low-Port Tree Representations....Pages 66-76
Fully Dynamic Representations of Interval Graphs....Pages 77-87
The Parameterized Complexity of Some Minimum Label Problems....Pages 88-99
Exact and Parameterized Algorithms for Max Internal Spanning Tree ....Pages 100-111
An Exact Algorithm for Minimum Distortion Embedding....Pages 112-121
Sub-coloring and Hypo-coloring Interval Graphs....Pages 122-132
Parameterized Complexity of Generalized Domination Problems....Pages 133-142
Connected Feedback Vertex Set in Planar Graphs....Pages 143-153
Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract)....Pages 154-165
On Module-Composed Graphs....Pages 166-177
An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees....Pages 178-189
The k-Disjoint Paths Problem on Chordal Graphs....Pages 190-201
Local Algorithms for Edge Colorings in UDGs....Pages 202-213
Directed Rank-Width and Displit Decomposition....Pages 214-225
An Algorithmic Study of Switch Graphs....Pages 226-237
Hardness Results and Efficient Algorithms for Graph Powers....Pages 238-249
Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph....Pages 250-261
Injective Oriented Colourings....Pages 262-272
Chordal Digraphs....Pages 273-284
A New Intersection Model and Improved Algorithms for Tolerance Graphs....Pages 285-295
Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes....Pages 296-307
Distance d -Domination Games....Pages 308-319
Cycles, Paths, Connectivity and Diameter in Distance Graphs....Pages 320-328
Smallest Odd Holes in Claw-Free Graphs (Extended Abstract)....Pages 329-340
Finding Induced Paths of Given Parity in Claw-Free Graphs....Pages 341-352
Back Matter....Pages -

✦ Subjects

Discrete Mathematics in Computer Science; Geometry; Algorithms; Symbolic and Algebraic Manipulation; Algorithm Analysis and Problem Complexity; Data Structures