Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

DOI10.1137/1.9781611974782.55MaRDI QIDQ4575794zbMATH OpenOpenAlexFDO

Authors Yixin Cao, R. B. Sandeep

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.55

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational methods for sparse matrices (65F50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Minimum fill-in: inapproximability and almost tight lower bounds
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• scientific article; zbMATH DE number 1775386
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• The General Minimum Fill-In Problem
• Subexponential parameterized algorithm for minimum fill-in
• scientific article; zbMATH DE number 7053390
• Faster Parameterized Algorithms for Minimum Fill-In

Cited in

(8)

• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• Minimum fill-in of sparse graphs: kernelization and approximation
• Minimum fill-in: inapproximability and almost tight lower bounds
• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• On the minimum chordal completion polytope
• Approximation algorithms in combinatorial scientific computing
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• On the effectiveness of the incremental approach to minimal chordal edge modification

This page was built for publication: Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

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