A local 2-approximation algorithm for the vertex cover problem
| Contribuinte(s) |
University of Helsinki, Department of Computer Science University of Helsinki, Helsinki Institute for Information Technology HIIT University of Helsinki, Helsinki Institute for Information Technology HIIT 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 distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem. |
| Formato |
15 |
| Identificador | |
| Idioma(s) |
eng |
| Relação |
23rd International Symposium on Distributed Computing (DISC) Distributed Computing 23rd International Symposium, DISC 2009. Elche, Spain, September 23–25, 2009. Proceedings Lecture Notes in Computer Science |
| Direitos |
The original publication is available at www.springerlink.com. |
| Fonte |
Åstrand , M , Floreen , P , Polishchuk , V , Rybicki , J , Suomela , J & Uitto , J 2009 , ' A local 2-approximation algorithm for the vertex cover problem ' , in Distributed Computing : 23rd International Symposium, DISC 2009. Elche, Spain, September 23–25, 2009. Proceedings , pp. 191-205 Lecture Notes in Computer Science , vol. 5805 . |
| Palavras-Chave | #113 Computer and information sciences |
| Tipo |
A4 Article in conference publication (refereed) textfile info:eu-repo/semantics/conferencePaper info:eu-repo/semantics/acceptedVersion |
