Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-04355-0_21 | DISC |
Keywords | Field | DocType |
weighted version,maximum degree,minimum vertex cover problem,synchronous communication round,2-approximation algorithm,vertex cover,synchronous communication | Approximation algorithm,Asynchronous communication,Graph,Combinatorics,Edge cover,Computer science,Vertex (graph theory),Vertex cover,Degree (graph theory),Feedback vertex set | Conference |
Volume | ISSN | ISBN |
5805 | 0302-9743 | 3-642-04354-2 |
Citations | PageRank | References |
20 | 0.75 | 15 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matti Åstrand | 1 | 46 | 2.23 |
| Patrik Floréen | 2 | 386 | 36.15 |
| Valentin Polishchuk | 3 | 252 | 34.51 |
| Joel Rybicki | 4 | 78 | 9.69 |
| Jukka Suomela | 5 | 600 | 46.99 |
| Jara Uitto | 6 | 107 | 17.08 |