This book constitutes the thoroughly refereed post-proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005, held in Metz, France in June 2005.
The 38 revised full papers presented together with 2 invited papers were carefully selected from 125 submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms, and graph-theoretical applications in various fields. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in Computer Science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions of future research.
Author(s): Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, Francesco Scarcello (auth.), Dieter Kratsch (eds.)
Series: Lecture Notes in Computer Science 3787 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 478
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Data Structures; Computer Graphics; Algorithms
Front Matter....Pages -
Hypertree Decompositions: Structure, Algorithms, and Applications....Pages 1-15
Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey....Pages 16-27
Domination Search on Graphs with Low Dominating-Target-Number....Pages 28-37
Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs....Pages 38-48
Approximating Rank-Width and Clique-Width Quickly....Pages 49-58
Computing the Tutte Polynomial on Graphs of Bounded Clique-Width....Pages 59-68
Minimizing NLC-Width is NP-Complete....Pages 69-80
Channel Assignment and Improper Choosability of Graphs....Pages 81-90
Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time....Pages 91-102
Roman Domination over Some Graph Classes....Pages 103-114
Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms....Pages 115-126
Network Discovery and Verification....Pages 127-138
Complete Graph Drawings Up to Triangle Mutations....Pages 139-150
Collective Tree 1-Spanners for Interval Graphs....Pages 151-162
On Stable Cutsets in Claw-Free Graphs and Planar Graphs....Pages 163-174
Induced Subgraphs of Bounded Degree and Bounded Treewidth....Pages 175-186
Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time....Pages 187-198
Ultimate Generalizations of LexBFS and LEX M....Pages 199-213
Adding an Edge in a Cograph....Pages 214-226
The Computational Complexity of Delay Management....Pages 227-238
Acyclic Choosability of Graphs with Small Maximum Degree....Pages 239-248
Generating Colored Trees....Pages 249-260
Optimal Hypergraph Tree-Realization....Pages 261-270
Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints....Pages 271-282
On the Fixed-Parameter Enumerability of Cluster Editing....Pages 283-294
Locally Consistent Constraint Satisfaction Problems with Binary Constraints....Pages 295-306
On Randomized Broadcasting in Star Graphs....Pages 307-318
Finding Disjoint Paths on Directed Acyclic Graphs....Pages 319-330
Approximation Algorithms for the Bi-criteria Weighted max-cut Problem....Pages 331-340
Approximation Algorithms for the Weighted Independent Set Problem....Pages 341-350
Approximation Algorithms for Unit Disk Graphs....Pages 351-361
Computation of Chromatic Polynomials Using Triangulations and Clique Trees....Pages 362-373
Computing Branchwidth Via Efficient Triangulations and Blocks....Pages 374-384
Algorithms Based on the Treewidth of Sparse Graphs....Pages 385-396
Extending the Tractability Border for Closest Leaf Powers....Pages 397-408
Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model....Pages 409-420
Algebraic Operations on PQ Trees and Modular Decomposition Trees....Pages 421-432
Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs....Pages 433-444
Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny....Pages 445-455
Recognizing HHDS-Free Graphs....Pages 456-467
Back Matter....Pages -
