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
