Treewidth and Minimum Fill-in: Grouping the Minimal Separators
From MaRDI portal
Publication:2784449
DOI10.1137/S0097539799359683zbMath0987.05085MaRDI QIDQ2784449
Vincent Bouchitte, Ioan Todinca
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (70)
Minimal triangulations of graphs: a survey ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Experimental Analysis of Treewidth ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ Approximation algorithms for treewidth ⋮ Constructing Brambles ⋮ Treewidth computation and extremal combinatorics ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ 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 ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Excluding hooks and their complements ⋮ Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph ⋮ Graphs with polynomially many minimal separators ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Some results on connected vertex separators ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Generating weakly chordal graphs from arbitrary graphs ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Positive-instance driven dynamic programming for treewidth ⋮ A Characterisation of the Minimal Triangulations of Permutation Graphs ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Approximating the treewidth of AT-free graphs. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing hypergraph width measures exactly ⋮ Chordal embeddings of planar graphs ⋮ Unnamed Item ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ On treewidth approximations. ⋮ Treewidth lower bounds with brambles ⋮ On the Maximum Weight Minimal Separator ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Minimal separators in extended \(P_4\)-laden graphs ⋮ Minimal split completions ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Graphical models for genetic analyses ⋮ Tree decompositions with small cost ⋮ Computing the branchwidth of interval graphs ⋮ Characterizing and computing minimal cograph completions ⋮ On the complexity of computing treelength ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Unnamed Item ⋮ Finding cut-vertices in the square roots of a graph ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ On \(H\)-topological intersection graphs ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ Unnamed Item ⋮ Linear separation of connected dominating sets in graphs ⋮ Unnamed Item ⋮ On a property of minimal triangulations ⋮ On the Number of Minimal Separators in Graphs ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Positive-Instance Driven Dynamic Programming for Treewidth. ⋮ Finding small-width connected path decompositions in polynomial time ⋮ On the maximum weight minimal separator ⋮ On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five ⋮ Unnamed Item
This page was built for publication: Treewidth and Minimum Fill-in: Grouping the Minimal Separators
