A simple local 3-approximation algorithm for vertex cover

Show full item record




Information Processing Letters, volume 109, issue 12, pages 642–645, 2009

Title: A simple local 3-approximation algorithm for vertex cover
Author: Polishchuk, Valentin; Suomela, Jukka
Contributor organization: Department of Computer Science
Tietojenkäsittelytieteen laitos
Datavetenskap, Institutionen för
Publisher: Elsevier
Date: 2009-05-31
Language: eng
DOI: https://doi.org/10.1016/j.ipl.2009.02.017
URI: http://hdl.handle.net/10138/1205
Abstract: 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.

Files in this item

Total number of downloads: Loading...

Files Size Format View
polishchuk-2009-simple.pdf 142.5Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record