New approximation algorithms for minimum weighted edge cover

DOI10.1137/1.9781611975215.10MaRDI QIDQ6539158zbMATH OpenFDO

Authors S. M. Ferdous, Alex Pothen, A. Khan

Publication date 14 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611975215.10

Mathematics Subject Classification ID

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

Recommendations

• A new 3/2-approximation algorithm for the \(b\)-\textsc{Edge Cover} problem
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• An approximation algorithm for the minimum weighted vertex-cover problem
• scientific article; zbMATH DE number 2119674
• A simple LP-free approximation algorithm for the minimum weight vertex cover problem

Cited in

(2)

• A new 3/2-approximation algorithm for the \(b\)-\textsc{Edge Cover} problem
• An o(n n)-time approximation scheme for geometric many-to-many matching

This page was built for publication: New approximation algorithms for minimum weighted edge cover

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