Name
Abstract | ||
|---|---|---|
We give deterministic distributed algorithms that given 茂戮驴 0 find in a planar graph G, (1±茂戮驴)-approximations of a maximum independent set, a maximum matching, and a minimum dominating set. The algorithms run in O(log*|G|) rounds. In addition, we prove that no faster deterministic approximation is possible and show that if randomization is allowed it is possible to beat the lower bound for deterministic algorithms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-87779-0_6 | DISC |
Keywords | Field | DocType |
maximum independent set,algorithms run,deterministic algorithm,minimum dominating set,planar graphs,planar graph,maximum matching,deterministic approximation,distributed algorithm | Discrete mathematics,Combinatorics,Upper and lower bounds,Planar straight-line graph,Matching (graph theory),Independent set,Distributed algorithm,Planar graph,Mathematics,Minimum dominating set | Conference |
Volume | ISSN | Citations |
5218 | 0302-9743 | 55 |
PageRank | References | Authors |
1.96 | 24 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Czygrinow | 1 | 227 | 25.81 |
| Michal Hanćkowiak | 2 | 101 | 6.56 |
| Wojciech Wawrzyniak | 3 | 97 | 8.23 |