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

DOI10.1007/S00453-010-9421-1zbMATH Open1230.68100OpenAlexW2124174860WikidataQ59567595 ScholiaQ59567595MaRDI QIDQ652537FDOQ652537

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

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

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)

Cites Work

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

Cited In (19)

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

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)