Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
From MaRDI portal
Publication:2656894
Recommendations
Cites work
- scientific article; zbMATH DE number 861332 (Why is no real title available?)
- scientific article; zbMATH DE number 1420906 (Why is no real title available?)
- scientific article; zbMATH DE number 7378380 (Why is no real title available?)
- A complexity dichotomy and a new boundary class for the dominating set problem
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic graph theory and perfect graphs
- Characterizations and algorithmic applications of chordal graph embeddings
- Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem
- Clique-cutsets beyond chordal graphs
- Clique-width for 4-vertex forbidden subgraphs
- Clique-width for hereditary graph classes
- Computing the treewidth and the minimum fill-in with the modular decomposition
- Decomposition by clique separators
- Efficient subgraphs packing
- Finding induced subgraphs via minimal triangulations
- Large Induced Subgraphs via Triangulations and CMSO
- Linear separation of connected dominating sets in graphs
- Listing all potential maximal cliques of a graph
- Minimal separators in \(P_4\)-sparse graphs
- Minimal separators in extended \(P_4\)-laden graphs
- Minimal separators in graph classes defined by small forbidden induced subgraphs
- Minimal triangulations of graphs: a survey
- Minimum Fill-in on Circle and Circular-Arc Graphs
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- On graphs with polynomially solvable maximum-weight clique problem
- On rigid circuit graphs
- On the complexity of H-coloring
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Oriented star packings
- Paw-free graphs
- STACS 2005
- Safe separators for treewidth
- Separability generalizes Dirac's theorem
- Separator orders in interval, cocomparability, and AT-free graphs
- TREEWIDTH OF CIRCLE GRAPHS
- The price of connectivity for cycle transversals
- To approximate treewidth, use treelength!
- Tournaments and colouring
- Towards an isomorphism dichotomy for hereditary graph classes
- Treewidth and Pathwidth of Permutation Graphs
- Treewidth and minimum fill-in: Grouping the minimal separators
- Treewidth computations. I: Upper bounds
- Treewidth. Computations and approximations
Cited in
(5)- A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs
- A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number
- Comparison of k-creature and t-critter
- Taming graphs with no large creatures and skinny ladders
- Taming graphs with no large creatures and skinny ladders
This page was built for publication: Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656894)
