Graph-Theoretic Concepts in Computer Science 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers / edited by Dieter Kratsch.

Saved in:
Bibliographic Details
Corporate Author: SpringerLink (Online service)
Other Authors: Kratsch, Dieter. (Editor,
Format: eBook
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2005.
Edition:1st ed. 2005.
Series:Theoretical Computer Science and General Issues ; 3787
Springer eBook Collection.
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • 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 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.