The minimum generalized vertex cover problem

DOI10.1145/1125994.1125998MaRDI QIDQ2944506zbMATH OpenOpenAlexFDO

Authors Refael Hassin, Asaf Levin

Publication date 2 September 2015

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1125994.1125998

zbMATH Keywords

complexity classificationlocal ratiovertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Algorithms - ESA 2003
• scientific article; zbMATH DE number 3869066
• Capacitated vertex covering
• scientific article; zbMATH DE number 3853131
• scientific article; zbMATH DE number 2119748

Cited in

(19)

• Minimum-weight vertex cover problem for two-class resource connection graphs
• The generalized vertex cover problem and some variations
• On the minimum vertex cover of generalized Petersen graphs
• A dual-fitting \(\frac{3}{2}\)-approximation algorithm for some minimum-cost graph problems
• Minimum vertex cover in generalized random graphs with power law degree distribution
• Results on the min-sum vertex cover problem
• The Balanced Edge Cover Problem
• The Probabilistic Minimum Vertex-covering Problem
• Exact solutions to generalized vertex covering problems: a comparison of two models
• Minimum scan cover with angular transition costs
• Algorithms - ESA 2003
• Minimum cost edge subset covering exactly k vertices of a graph
• Approximating power node-deletion problems
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Matroid-constrained vertex cover
• Approximating power node-deletion problems
• On the multi-radius cover problem
• NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting
• Min sum clustering with penalties

This page was built for publication: The minimum generalized vertex cover problem

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