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




Related Items (34)

On Cutwidth Parameterized by Vertex CoverApproximately counting locally-optimal structuresApproximately Counting Locally-Optimal StructuresConstructing BramblesTreewidth computation and extremal combinatoricsFinding optimal triangulations parameterized by edge clique coverStrongly Chordal and Chordal Bipartite Graphs Are Sandwich MonotoneFinding a maximum minimal separator: graph classes and fixed-parameter tractabilityLarge Induced Subgraphs via Triangulations and CMSOTangle bases: RevisitedPositive-instance driven dynamic programming for treewidthA survey of parameterized algorithms and the complexity of edge modificationExact algorithms for edge dominationOn the hardness of inclusion-wise minimal separators enumerationComputing hypergraph width measures exactlyAcyclic and star colorings of cographsUnnamed ItemA revisit of the scheme for computing treewidth and minimum fill-inFaster parameterized algorithms for \textsc{Minimum Fill-in}Strongly chordal and chordal bipartite graphs are sandwich monotoneOn the Maximum Weight Minimal SeparatorOn cutwidth parameterized by vertex coverSolving Graph Problems via Potential Maximal CliquesBeyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliquesComputing tree-depth faster than \(2^n\)Algorithms parameterized by vertex cover and modular width, through potential maximal cliquesA note on exact algorithms for vertex ordering problems on graphsOn the complexity of computing treelengthOn listing, sampling, and counting the chordal graphs with edge constraintsUnnamed ItemOn the Number of Minimal Separators in GraphsPositive-Instance Driven Dynamic Programming for Treewidth.On the maximum weight minimal separatorUnnamed Item




This page was built for publication: Exact Algorithms for Treewidth and Minimum Fill-In