A decomposition strategy for the vertex cover problem

DOI10.1016/0020-0190(89)90091-4MaRDI QIDQ1123907zbMATH OpenOpenAlexFDO

Authors P. Bertolazzi, Antonio Sassano

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0020-0190(89)90091-4

zbMATH Keywords

decompositionminorclutterstable setminimum weight vertex cover problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A graph approximation heuristic for the vertex cover problem on planar graphs
• scientific article; zbMATH DE number 3853131
• The Probabilistic Minimum Vertex-covering Problem
• Crown reductions for the minimum weighted vertex cover problem
• A polynomial time solvable instance of the feasible minimum cover problem

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 3513839 (Why is no real title available?)
• A Class of Polynomially Solvable Set-Covering Problems
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• The NP-completeness column: an ongoing guide
• The matroids with the max-flow min-cut property

Cited in

(6)

• A novel decomposition approach to set covering problems by exploiting special structures
• A neural network for the minimum set covering problem
• Core influence mechanism on vertex-cover problem through leaf-removal-core breaking
• A polynomial time solvable instance of the feasible minimum cover problem
• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space

This page was built for publication: A decomposition strategy for the vertex cover problem

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