Faster parameterized algorithms for \textsc{Minimum Fill-in}
From MaRDI portal
Publication:652537
DOI10.1007/s00453-010-9421-1zbMath1230.68100OpenAlexW2124174860WikidataQ59567595 ScholiaQ59567595MaRDI QIDQ652537
Pinar Heggernes, Hans L. Bodlaender, 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
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
What’s Next? Future Directions in Parameterized Complexity, A survey of parameterized algorithms and the complexity of edge modification, Unnamed Item, Solving Graph Problems via Potential Maximal Cliques, Searching for better fill-in, Minimum fill-in of sparse graphs: kernelization and approximation, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Unnamed Item, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- Minimal triangulations of graphs: a survey
- A vertex incremental approach for maintaining chordality
- Chordal completions of planar graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Characterizations and algorithmic applications of chordal graph embeddings
- Listing all potential maximal cliques of a graph
- A characterisation of rigid circuit graphs
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- 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
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Treewidth Computation and Extremal Combinatorics
- 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
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
