Name
Abstract | ||
|---|---|---|
The greedy sequential algorithm for maximal independent set (MIS) loops over the vertices in an arbitrary order adding a vertex to the resulting set if and only if no previous neighboring vertex has been added. In this loop, as in many sequential loops, each iterate will only depend on a subset of the previous iterates (i.e. knowing that any one of a vertex's previous neighbors is in the MIS, or knowing that it has no previous neighbors, is sufficient to decide its fate one way or the other). This leads to a dependence structure among the iterates. If this structure is shallow then running the iterates in parallel while respecting the dependencies can lead to an efficient parallel implementation mimicking the sequential algorithm. In this paper, we show that for any graph, and for a random ordering of the vertices, the dependence length of the sequential greedy MIS algorithm is polylogarithmic (O(log^2 n) with high probability). Our results extend previous results that show polylogarithmic bounds only for random graphs. We show similar results for greedy maximal matching (MM). For both problems we describe simple linear-work parallel algorithms based on the approach. The algorithms allow for a smooth tradeoff between more parallelism and reduced work, but always return the same result as the sequential greedy algorithms. We present experimental results that demonstrate efficiency and the tradeoff between work and parallelism. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2312005.2312058 | acm symposium on parallel algorithms and architectures |
Keywords | DocType | Volume |
sequential greedy mis algorithm,greedy sequential algorithm,previous neighboring vertex,sequential loop,previous neighbor,greedy maximal matching,sequential algorithm,sequential greedy algorithm,previous iterates,previous result,sequential maximal independent set,random graph,parallel algorithms,greedy algorithm,maximal independent set,maximal matching,parallel algorithm | Conference | abs/1202.3205 |
Citations | PageRank | References |
18 | 0.62 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guy E. Blelloch | 1 | 2927 | 207.30 |
| Jeremy T. Fineman | 2 | 587 | 36.10 |
| Julian Shun | 3 | 593 | 32.57 |