Graph-Theoretic Concepts in Computer Science | 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers | ISBN 9783540310006

Graph-Theoretic Concepts in Computer Science

31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers

herausgegeben von Dieter Kratsch
Buchcover Graph-Theoretic Concepts in Computer Science  | EAN 9783540310006 | ISBN 3-540-31000-2 | ISBN 978-3-540-31000-6

Graph-Theoretic Concepts in Computer Science

31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers

herausgegeben von Dieter Kratsch

Inhaltsverzeichnis

  • 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.