A polynomial time solvable instance of the feasible minimum cover problem

DOI10.1016/S0020-0190(98)00154-9MaRDI QIDQ293433zbMATHFDO

Authors Chor-Ping Low

Publication date 9 June 2016

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

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001549?np=y

zbMATH Keywords

bipartite graphvertex coverpolynomial time algorithmmaximum matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Polynomially solvable cases of the minimum biclique vertex-cover problem
• Publication:4941917
• Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• A decomposition strategy for the vertex cover problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3299758 (Why is no real title available?)
• A new class of efficient algorithms for reconfiguration of memory arrays
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Coverings of Bipartite Graphs
• Matching theory
• TWO THEOREMS IN GRAPH THEORY
• The uniquely solvable bipartite matching problem

Cited in

(5)

• A decomposition strategy for the vertex cover problem
• Polynomial time approximation schemes for minimum disk cover problems
• Minimum constellation covers: hardness, approximability and polynomial cases
• Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations
• Polynomially solvable cases of the minimum biclique vertex-cover problem

This page was built for publication: A polynomial time solvable instance of the feasible minimum cover problem

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