Graph-Theoretic Concepts in Computer Science: 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers (Lecture Notes in Computer Science, 3787)

✍ Scribed by Dieter Kratsch (editor)

• Publisher: Springer
• Year: 2005
• Tongue: English
• Leaves: 481
• Category: Library

✦ Synopsis

The 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005) was held on the campus "Ile du Saulcy" of the Univ- sity Paul Verlaine-Metz in France. The workshop was organized by the La- ratoire d'Informatique Th´ eorique et Appliqu´ ee (LITA) and it took place June 23 - 25 2005. The 94 participants of WG 2005 came from universities and - search institutes of 18 di?erent countries. The WG 2005 workshop continues the series of 30 previous WG workshops. Since 1975, WG has taken place 20 times in Germany, four times in The Neth- lands, twotimesinAustriaaswellasonceinItaly, inSlovakia, inSwitzerlandand inCzechRepublic, andhas nowbeen heldfor the ?rsttime inFrance.The wo- shop 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. The talks were given in the "Petit Th´ eatre". They showed how recent research results from algori- mic graph theory can be used in computer science and which graph-theoretic questions arise from new developments in computer science. There were two fascinating invited lectures by Georg Gottlob (Vienna, Austria) and Gregory Kucherov (Nancy, France).

✦ Table of Contents

Frontmatter
Invited Lectures
Hypertree Decompositions: Structure, Algorithms, and Applications
Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey
Regular Papers
Domination Search on Graphs with Low Dominating-Target-Number
Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs
Approximating Rank-Width and Clique-Width Quickly
Computing the Tutte Polynomial on Graphs of Bounded Clique-Width
Minimizing NLC-Width is NP-Complete
Channel Assignment and Improper Choosability of Graphs
Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time
Roman Domination over Some Graph Classes
Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms
Network Discovery and Verification
Complete Graph Drawings Up to Triangle Mutations
Collective Tree 1-Spanners for Interval Graphs
On Stable Cutsets in Claw-Free Graphs and Planar Graphs
Induced Subgraphs of Bounded Degree and Bounded Treewidth
Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time
Ultimate Generalizations of LexBFS and LEX M
Adding an Edge in a Cograph
The Computational Complexity of Delay Management
Acyclic Choosability of Graphs with Small Maximum Degree
Generating Colored Trees
Optimal Hypergraph Tree-Realization
Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints
On the Fixed-Parameter Enumerability of Cluster Editing
Locally Consistent Constraint Satisfaction Problems with Binary Constraints
On Randomized Broadcasting in Star Graphs
Finding Disjoint Paths on Directed Acyclic Graphs
Approximation Algorithms for the Bi-criteria Weighted {\sc max-cut} Problem
Approximation Algorithms for the Weighted Independent Set Problem
Approximation Algorithms for Unit Disk Graphs
Computation of Chromatic Polynomials Using Triangulations and Clique Trees
Computing Branchwidth Via Efficient Triangulations and Blocks
Algorithms Based on the Treewidth of Sparse Graphs
Extending the Tractability Border for Closest Leaf Powers
Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model
Algebraic Operations on PQ Trees and Modular Decomposition Trees
Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs
Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny
Recognizing HHDS-Free Graphs
Backmatter