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

DOI10.1016/J.TCS.2014.03.013zbMATH Open1358.05278OpenAlexW2023952346MaRDI QIDQ2441783FDOQ2441783

Authors: 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

Recommendations

• Exact Algorithms for Treewidth and Minimum Fill-In
• Automata, Languages and Programming
• Searching for better fill-in
• Searching for better fill-in
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm

zbMATH Keywords

treewidthminimal separatorminimum fill-inpotential maximal clique

Mathematics Subject Classification ID

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

Cites Work

• Treewidth computation and extremal combinatorics
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Listing all potential maximal cliques of a graph
• Tree decompositions with small cost
• Treewidth and minimum fill-in: Grouping the minimal separators
• Finding induced subgraphs via minimal triangulations
• Exact Algorithms for Treewidth and Minimum Fill-In
• The Pathwidth and Treewidth of Cographs
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• Treewidth of Chordal Bipartite Graphs
• On the Complexity of Computing Treelength
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Two strikes against perfect phylogeny
• Computing hypergraph width measures exactly
• Treewidth of Circular-Arc Graphs
• Minimum Fill-in on Circle and Circular-Arc Graphs
• TREEWIDTH OF CIRCLE GRAPHS
• Title not available (Why is that?)

Cited In (6)

• Title not available (Why is that?)
• Approximately counting locally-optimal structures
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• Finding optimal triangulations parameterized by edge clique cover
• Automata, Languages and Programming
• Approximately Counting Locally-Optimal Structures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441783)