A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover

Preprint

18 May 2002

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.cs/0205037

Abstract

The paper describes a simple deterministic parallel/distributed (2+epsilon)-approximation algorithm for the minimum-weight vertex-cover problem and its dual (edge/element packing).

Keywords

APPROXIMATION TECHNIQUE
PARALLEL APPROXIMATION
DUAL PARALLEL
VERTEX COVER
PRIMAL DUAL
ALGORITHM

All Related Versions

Version 1, 2002-05-18, ArXiv
Published version: Journal of Algorithms, 17 (2), 280.

This publication has 0 references indexed in Scilit: