A revisit of the scheme for computing treewidth and minimum fill-in

DOI10.1016/J.TCS.2014.03.013zbMath1358.05278OpenAlexW2023952346MaRDI QIDQ2441783

Masanobu Furuse, Koichi Yamazaki

Publication date: 28 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.03.013

zbMATH Keywords

treewidthminimal separatorminimum fill-inpotential maximal clique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Unnamed Item ⋮ Solving Graph Problems via Potential Maximal Cliques

Cites Work

• Unnamed Item
• Computing hypergraph width measures exactly
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Listing all potential maximal cliques of a graph
• Tree decompositions with small cost
• Treewidth computation and extremal combinatorics
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Finding Induced Subgraphs via Minimal Triangulations
• On the Complexity of Computing Treelength
• Exact Algorithms for Treewidth and Minimum Fill-In
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth of Circular-Arc Graphs
• The Pathwidth and Treewidth of Cographs
• Treewidth of Chordal Bipartite Graphs
• TREEWIDTH OF CIRCLE GRAPHS
• Two strikes against perfect phylogeny
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs

This page was built for publication: A revisit of the scheme for computing treewidth and minimum fill-in