Approximating the Minimum Chain Completion problem

DOI10.1016/J.IPL.2009.05.006zbMATH Open1202.68483OpenAlexW2005576669MaRDI QIDQ989547FDOQ989547

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

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

zbMATH Keywords

approximation algorithmsvertex coverchain graphsmin cutMax flow

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• Critical Load Factors in Two-Processor Distributed Systems
• Computing the Minimum Fill-In is NP-Complete
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem

Cited In (5)

• On the Chain Pair Simplification Problem
• Title not available (Why is that?)
• 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)