Approximating the Minimum Chain Completion problem

DOI10.1016/j.ipl.2009.05.006zbMath1202.68483OpenAlexW2005576669MaRDI QIDQ989547

Tomás Feder, Evimaria Terzi, Heikki Mannila

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.05.006

zbMATH Keywords

chain graphsapproximation algorithmsMax flowvertex covermin cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (4)

Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Approximation Algorithms for Minimum Chain Vertex Deletion ⋮ On the threshold of intractability ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Computing the Minimum Fill-In is NP-Complete
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Critical Load Factors in Two-Processor Distributed Systems
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• A Fast Parametric Maximum Flow Algorithm and Applications

This page was built for publication: Approximating the Minimum Chain Completion problem