A Polynomial Approximation Algorithm for the Minimum Fill-In Problem

DOI10.1137/S0097539798336073zbMath0969.68194OpenAlexW2030064859MaRDI QIDQ4507385

Ron Shamir, Assaf Natanzon, 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

graph algorithmschain graphschordal graphsapproximation algorithmsparameterized algorithmschordal completionminimum fill-inchain completion

Mathematics Subject Classification ID

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

Related Items (25)

Minimal triangulations of graphs: a survey ⋮ On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Estimating the number of connected components in a graph via subgraph sampling ⋮ Linear optimization over homogeneous matrix cones ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Searching for better fill-in ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ On listing, sampling, and counting the chordal graphs with edge constraints ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Complexity classification of some edge modification problems ⋮ Approximating the Minimum Chain Completion problem ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals ⋮ Unnamed Item ⋮ Approximation Algorithms for Minimum Chain Vertex Deletion ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Unnamed Item ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Unnamed Item ⋮ Unnamed Item

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