Safe separators for treewidth
From MaRDI portal
Publication:819825
DOI10.1016/j.disc.2005.12.017zbMath1084.05065OpenAlexW2066867008WikidataQ59567815 ScholiaQ59567815MaRDI QIDQ819825
Arie M. C. A. Koster, Hans L. Bodlaender
Publication date: 29 March 2006
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/22166
Related Items
Minimal triangulations of graphs: a survey ⋮ Safe separators for treewidth ⋮ Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ An introduction to clique minimal separator decomposition ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Positive-instance driven dynamic programming for treewidth ⋮ Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs ⋮ Induced subgraphs and tree decompositions V. one neighbor in a hole ⋮ Revisiting Decomposition by Clique Separators ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ Treewidth lower bounds with brambles ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ On the complexity of computing treebreadth ⋮ Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization ⋮ Tractable answer-set programming with weight constraints: bounded treewidth is not enough ⋮ Peptide sequencing via graph path decomposition ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Characterizing and computing minimal cograph completions ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ On the maximum cardinality search lower bound for treewidth ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ BWM*: A Novel, Provable, Ensemble-Based Dynamic Programming Algorithm for Sparse Approximations of Computational Protein Design ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Positive-Instance Driven Dynamic Programming for Treewidth. ⋮ Computing treewidth on the GPU ⋮ On sparsification for computing treewidth ⋮ Characterizing Tseitin-formulas with short regular resolution refutations
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monadic second-order evaluations on tree-decomposable graphs
- Improved algorithms for graph four-connectivity
- Safe separators for treewidth
- Decomposition by clique separators
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- A partial k-arboretum of graphs with bounded treewidth
- A practical algorithm for making filled graphs minimal
- Optimal decomposition by clique separators
- Easy problems for tree-decomposable graphs
- Algorithms for Radio Link Frequency Assignment: The Calma Project
- Characterization and Recognition of Partial 3-Trees
- Complexity of Finding Embeddings in a k-Tree
- Dividing a Graph into Triconnected Components
- Solving partial constraint satisfaction problems with tree decomposition
- Depth-First Search and Linear Graph Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
