Minimum fill-in: inapproximability and almost tight lower bounds
From MaRDI portal
Publication:2304536
DOI10.1016/j.ic.2020.104514zbMath1435.68111arXiv1606.08141OpenAlexW3000704721WikidataQ126345508 ScholiaQ126345508MaRDI QIDQ2304536
Publication date: 12 March 2020
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.08141
Computational methods for sparse matrices (65F50) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
A survey of parameterized algorithms and the complexity of edge modification ⋮ Sums of Squares and Sparse Semidefinite Programming ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ On subgraph complementation to \(H\)-free Graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The analysis of a nested dissection algorithm
- Optimization, approximation, and complexity classes
- Some simplified NP-complete graph problems
- Chordal completions of planar graphs
- Some APX-completeness results for cubic graphs
- Which problems have strongly exponential complexity?
- On subexponential and FPT-time inapproximability
- Graph expansion and the unique games conjecture
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Interval Completion Is Fixed Parameter Tractable
- Complexity of Finding Embeddings in a k-Tree
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- Node-Deletion Problems on Bipartite Graphs
- 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
- Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
- Inapproximability of Treewidth and Related Problems
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Parameterized Algorithms
- Nested Dissection of a Regular Finite Element Mesh
- The PCP theorem by gap amplification
- On the complexity of \(k\)-SAT
This page was built for publication: Minimum fill-in: inapproximability and almost tight lower bounds
