
×
Graph-Theoretic Concepts in Computer Science
31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers
herausgegeben von Dieter KratschInhaltsverzeichnis
- 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.