An approximation algorithm for the minimum weighted vertex-cover problem

MaRDI QIDQ2991224zbMATH OpenFDO

Authors Lei Kou, Xiaochuan Cui, Jingrong Chen

Publication date 10 August 2016

zbMATH Keywords

approximate algorithmDijkstra algorithmminimum weighted vertex-cover problemtime complex

Mathematics Subject Classification ID

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

Recommendations

• Minimum vertex covering problem based on the shortest path algorithm
• scientific article; zbMATH DE number 3869066
• A simple LP-free approximation algorithm for the minimum weight vertex cover problem
• An edge-reduction algorithm for the vertex cover problem
• scientific article; zbMATH DE number 3853131

Cited in

(12)

• Approximation algorithms for minimum weight connected 3-path vertex cover
• Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problem
• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• Minimum vertex covering problem based on the shortest path algorithm
• scientific article; zbMATH DE number 5631194 (Why is no real title available?)
• scientific article; zbMATH DE number 709680 (Why is no real title available?)
• An articulation point-based approximation algorithm for minimum vertex cover problem
• Algorithmic Applications in Management
• New approximation algorithms for minimum weighted edge cover
• A simple LP-free approximation algorithm for the minimum weight vertex cover problem
• A parallel algorithm for the minimum weighted vertex cover problem
• An ant colony optimization algorithm for the minimum weight vertex cover problem

This page was built for publication: An approximation algorithm for the minimum weighted vertex-cover problem

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