Graph-Theoretic Concepts in Computer Science : 32nd International Workshop, WG 2006, Bergen, Norway, June 22-23, 2006, Revised Papers

by Fomin, Fedor V.

• ISBN13: 9783540483816
• ISBN10: 3540483810
• Format: Paperback
• Copyright: 2006-06-30
• Publisher: Springer Verlag

Summary

This book constitutes the thoroughly refereed post-proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006, held in Bergen, Norway in June 2006. The 30 revised full papers presented together with 1 invited paper were carefully selected from 91 submissions. The papers address all aspects of graph-theoretic concepts in computer science such as 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 graph-theoretical applications in various fields.

Table of Contents

Treewidth: Characterizations, Applications, and Computations	p. 1
Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy	p. 15
Generalised Dualities and Finite Maximal Antichains	p. 27
Chordal Deletion Is Fixed-Parameter Tractable	p. 37
A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators	p. 49
Divide-and-Color	p. 58
Listing Chordal Graphs and Interval Graphs	p. 68
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs	p. 78
Improved Edge-Coloring with Three Colors	p. 90
Vertex Coloring of Comparability+ke and -ke Graphs	p. 102
Convex Drawings of Graphs with Non-convex Boundary	p. 113
How to Sell a Graph: Guidelines for Graph Retailers	p. 125
Strip Graphs: Recognition and Scheduling	p. 137
Approximating the Traffic Grooming Problem in Tree and Star Networks	p. 147
Bounded Arboricity to Determine the Local Structure of Sparse Graphs	p. 159
An Implicit Representation of Chordal Comparabilty Graphs in Linear-Time	p. 168
Partitioned Probe Comparability Graphs	p. 179
Computing Graph Polynomials on Graphs of Bounded Clique-Width	p. 191
Generation of Graphs with Bounded Branchwidth	p. 205
Minimal Proper Interval Completions	p. 217
Monotony Properties of Connected Visible Graph Searching	p. 229
Finding Intersection Models of Weakly Chordal Graphs	p. 241
A Fully Dynamic Algorithm for the Recognition of P[subscript 4]-Sparse Graphs	p. 256
Clique Graph Recognition Is NP-Complete	p. 269
Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms	p. 278
Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs	p. 289
Graph Labelings Derived from Models in Distributed Computing	p. 301
Flexible Matchings	p. 313
Simultaneous Graph Embeddings with Fixed Edges	p. 325
Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions	p. 336
Circular-Perfect Concave-Round Graphs	p. 348
Author Index	p. 357
Table of Contents provided by Ingram. All Rights Reserved.