A Polynomial Approximation Algorithm for the Minimum Fill-In Problem

DOI10.1137/S0097539798336073MaRDI QIDQ4507385zbMATH OpenOpenAlexFDO

Authors Assaf Natanzon, Ron Shamir, Roded Sharan

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsgraph algorithmschordal graphschain graphsparameterized algorithmschordal completionminimum fill-inchain completion

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph theory (05C99) Algorithms in computer science (68W99)

Recommendations

• scientific article; zbMATH DE number 1775386
• Subexponential parameterized algorithm for minimum fill-in
• Faster Parameterized Algorithms for Minimum Fill-In
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• Minimum fill-in of sparse graphs: kernelization and approximation

Cited in

(30)

• On the effectiveness of the incremental approach to minimal chordal edge modification
• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• On listing, sampling, and counting the chordal graphs with edge constraints
• Linear optimization over homogeneous matrix cones
• Polynomial kernels for edge modification problems towards block and strictly chordal graphs
• Searching for better fill-in
• Searching for better fill-in
• Approximating the Minimum Chain Completion problem
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Minimal triangulations of graphs: a survey
• Approximation algorithms in combinatorial scientific computing
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Complexity classification of some edge modification problems
• Robustness to dependency in portfolio optimization using overlapping marginals
• A survey of parameterized algorithms and the complexity of edge modification
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• Minimum fill-in: inapproximability and almost tight lower bounds
• On the minimum chordal completion polytope
• Minimum fill-in of sparse graphs: kernelization and approximation
• A revisited quadratic vertex-kernel for \textsc{Minimum Fill-In}
• Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• Exploring the subexponential complexity of completion problems
• Estimating the number of connected components in a graph via subgraph sampling
• Approximation algorithms for minimum chain vertex deletion
• An improved kernelization algorithm for trivially perfect editing
• scientific article; zbMATH DE number 1775386 (Why is no real title available?)

This page was built for publication: A Polynomial Approximation Algorithm for the Minimum Fill-In Problem

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