A simple local 3-approximation algorithm for vertex cover

Simple item page
dc.creatorPolishchuk, Valentin
dc.creatorSuomela, Jukka
dc.date2008-10-13
dc.date.accessioned2026-07-07T13:10:43Z
dc.date.available2026-07-07T13:10:43Z
dc.descriptionWe 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.
dc.description6 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/0810.2175
dc.identifierhttp://arxiv.org/abs/0810.2175
dc.identifierInformation Processing Letters 109 (2009) 642-645
dc.identifierdoi:10.1016/j.ipl.2009.02.017
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/229081
dc.subjectDistributed, Parallel, and Cluster Computing
dc.titleA simple local 3-approximation algorithm for vertex cover
dc.typetext

Files

Collections

arXiv