Faster parameterized algorithms for \textsc{Minimum Fill-in}

DOI10.1007/S00453-010-9421-1MaRDI QIDQ652537zbMATH OpenOpenAlexWikidataFDO

Authors Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger

Publication date 14 December 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-010-9421-1

zbMATH Keywords

chordal graphsfixed-parameter tractabilityparameterized algorithmsminimum fill-in

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• Faster Parameterized Algorithms for Minimum Fill-In
• scientific article; zbMATH DE number 7053390
• Subexponential parameterized algorithm for minimum fill-in
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• A characterisation of rigid circuit graphs
• A vertex incremental approach for maintaining chordality
• Characterizations and algorithmic applications of chordal graph embeddings
• Chordal completions of planar graphs
• Computing the Minimum Fill-In is NP-Complete
• Exact Algorithms for Treewidth and Minimum Fill-In
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Incidence matrices and interval graphs
• Listing all potential maximal cliques of a graph
• Minimal triangulations of graphs: a survey
• Moplex elimination orderings
• On rigid circuit graphs
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Treewidth Computation and Extremal Combinatorics
• Triangulated graphs and the elimination process

Cited in

(19)

• Subexponential parameterized algorithm for minimum fill-in
• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• scientific article; zbMATH DE number 7651188 (Why is no real title available?)
• What's next? Future directions in parameterized complexity
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• Searching for better fill-in
• Searching for better fill-in
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• Faster Parameterized Algorithms for Minimum Fill-In
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• A survey of parameterized algorithms and the complexity of edge modification
• The necessary and sufficient condition and the efficient algorithms for gradually varied fill
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Faster parameterized algorithms for minor containment
• Minimum fill-in of sparse graphs: kernelization and approximation
• Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
• scientific article; zbMATH DE number 1775386 (Why is no real title available?)
• A parameterized algorithm for chordal sandwich

This page was built for publication: Faster parameterized algorithms for \textsc{Minimum Fill-in}

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