A polynomial time solvable instance of the feasible minimum cover problem

DOI10.1016/S0020-0190(98)00154-9zbMATH Open1337.05101MaRDI QIDQ293433FDOQ293433

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

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

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)

Cites Work

• Title not available (Why is that?)
• Matching theory
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• TWO THEOREMS IN GRAPH THEORY
• The uniquely solvable bipartite matching problem
• Coverings of Bipartite Graphs
• A new class of efficient algorithms for reconfiguration of memory arrays

Cited In (4)

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

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)