Graph-Theoretic Concepts in Computer Science

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.