A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
From MaRDI portal
Publication:4507385
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
graph algorithmschain graphschordal graphsapproximation algorithmsparameterized algorithmschordal completionminimum fill-inchain completion
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99) Approximation algorithms (68W25) Algorithms in computer science (68W99)
Related Items
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
