A simple local 3-approximation algorithm for vertex cover
| Contribuinte(s) |
University of Helsinki, Helsinki Institute for Information Technology HIIT University of Helsinki, Helsinki Institute for Information Technology HIIT |
|---|---|
| Data(s) |
2009
|
| Resumo |
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. (c) 2009 Elsevier B.V. All rights reserved. |
| Formato |
4 |
| Identificador |
http://hdl.handle.net/10138/27927 0020-0190 |
| Idioma(s) |
eng |
| Publicador |
ELSEVIER BV |
| Relação |
Information Processing Letters |
| Fonte |
Polishchuk , V & Suomela , J 2009 , ' A simple local 3-approximation algorithm for vertex cover ' Information Processing Letters , vol 109 , no. 12 , pp. 642-645 . , 10.1016/j.ipl.2009.02.017 |
| Palavras-Chave | #113 Computer and information sciences |
| Tipo |
A1 Refereed journal article info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion |
