A simple local 3-approximation algorithm for vertex cover

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.
6 pages, 1 figure

Keywords

Distributed, Parallel, and Cluster Computing

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/229081

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0810.2175
 http://arxiv.org/abs/0810.2175
 Information Processing Letters 109 (2009) 642-645
 doi:10.1016/j.ipl.2009.02.017

Collections

arXiv