Approximating the Minimum Chain Completion problem

DOI10.1016/J.IPL.2009.05.006MaRDI QIDQ989547zbMATH OpenOpenAlexFDO

Authors Tomás Feder, Heikki Mannila, Evimaria Terzi

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

approximation algorithmsvertex coverchain graphsmin cutMax flow

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for minimum chain vertex deletion
• Recognition and combinatorial optimization algorithms for bipartite chain graphs
• On maximal chain subgraphs and covers of bipartite graphs
• A min-max property of chordal bipartite graphs with applications
• Clustering minimum biclique completion of a bipartite graph

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Computing the Minimum Fill-In is NP-Complete
• Critical Load Factors in Two-Processor Distributed Systems
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases

Cited in

(5)

• On the Chain Pair Simplification Problem
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• Approximation algorithms for minimum chain vertex deletion
• Recognition and combinatorial optimization algorithms for bipartite chain graphs
• On maximal chain subgraphs and covers of bipartite graphs

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

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