Subexponential Parameterized Algorithm for Minimum Fill-In
From MaRDI portal
Publication:5408764
DOI10.1137/11085390XzbMath1285.68055WikidataQ56430107 ScholiaQ56430107MaRDI QIDQ5408764
Yngve Villanger, Fedor V. Fomin
Publication date: 11 April 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (29)
Paths to Trees and Cacti ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Reducing rank of the adjacency matrix by graph modification ⋮ Reducing Rank of the Adjacency Matrix by Graph Modification ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Unnamed Item ⋮ Quick but odd growth of cacti ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Confronting intractability via parameters ⋮ Searching for better fill-in ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Quadratic vertex kernel for split vertex deletion ⋮ Paths to trees and cacti ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ A polynomial kernel for trivially perfect editing ⋮ Unnamed Item ⋮ On the threshold of intractability ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Editing to Connected F-Degree Graph ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
This page was built for publication: Subexponential Parameterized Algorithm for Minimum Fill-In
