A simple local 3-approximation algorithm for vertex cover
Permalink
Citation
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 |
View/ |