• Journal of Algorithms 17(2):280-289(1994); IPCO'93

  With Samir Khuller and Uzi Vishkin
  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). This paper was one of the first to use the primal-dual method for approximation in the distributed setting. This result was strengthened in `` Distributed and parallel algorithms for weighted vertex cover and other covering problems.''

  Journal version of [1993].

  • more...
  •   full text
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.