Exact Algorithms for Treewidth and Minimum Fill-In
From MaRDI portal
Publication:3631902
DOI10.1137/050643350zbMath1163.05320OpenAlexW2038049091WikidataQ60488730 ScholiaQ60488730MaRDI QIDQ3631902
Dieter Kratsch, Yngve Villanger, Ioan Todinca, Fedor V. Fomin
Publication date: 22 June 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1956/1151
treewidthminimal triangulationfill-inexact exponential algorithmminimal separatorspotential maximal clique
Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (34)
On Cutwidth Parameterized by Vertex Cover ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Constructing Brambles ⋮ Treewidth computation and extremal combinatorics ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Tangle bases: Revisited ⋮ Positive-instance driven dynamic programming for treewidth ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Exact algorithms for edge domination ⋮ On the hardness of inclusion-wise minimal separators enumeration ⋮ Computing hypergraph width measures exactly ⋮ Acyclic and star colorings of cographs ⋮ Unnamed Item ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ On the Maximum Weight Minimal Separator ⋮ On cutwidth parameterized by vertex cover ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Computing tree-depth faster than \(2^n\) ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ A note on exact algorithms for vertex ordering problems on graphs ⋮ On the complexity of computing treelength ⋮ On listing, sampling, and counting the chordal graphs with edge constraints ⋮ Unnamed Item ⋮ On the Number of Minimal Separators in Graphs ⋮ Positive-Instance Driven Dynamic Programming for Treewidth. ⋮ On the maximum weight minimal separator ⋮ Unnamed Item
This page was built for publication: Exact Algorithms for Treewidth and Minimum Fill-In