Loading...
Please wait, while we are loading the content...
Similar Documents
Notes on simple analysis for parallel maximal independent set and maximal matching algorithms (2013).
| Content Provider | CiteSeerX |
|---|---|
| Author | Shun, Julian |
| Abstract | For a graph G = (V, E) we use N(V) to denote the set of all neighbors of vertices in V. A maximal independent set U ⊂ V is thus one that satisfies N(U) ∩ U = ∅ and N(U) ∪ U = V. We use N(v) as a shorthand for N({v}) when v is a single vertex. We use G[U] to denote the vertex-induced subgraph of G by vertex set U, i.e., G[U] contains all vertices in U along with edges of G with both endpoints in U. A simple parallel algorithm due to Luby [3] for computing the maximal independent set is as follows: Algorithm 1 Luby’s algorithm for MIS 1: procedure MIS(G = (V, E)) 2: if V = 0 then return ∅ 3: else 4: randomly assign unique priorities πv to each v ∈ V 5: let W be the set of vertices in V with higher priority than all 6: of its neighbors (i.e. vertices v such that ∀u ∈ N(v), πv> πu) 7: V ′ = V \ (W ∪ N(W)) 8: return W ∪ MIS(G[V ′]) Theorem 1.1. Each recursive call to MIS removes half of the number of edges in G in expectation. Proof. Here is a simple analysis due to Métivier et. al. [4]: Consider an edge (u, v) in G. Define the indicator variable Xu to be the event that u’s priority is greater than that of all of its neighbors and all of v’s neighbors (excluding u itself). Note that if this event happens, u will be included in the MIS, and all edges incident to u and v will be removed. For the purpose of this analysis we say that if Xu happens, then u preemptively removes v and the edges incident to v. Note that any vertex can be preemptively removed at most once, and any edge (u, w) can only be preemptively removed twice, once when u is preemptively removed and once when w is preemptively removed. Note 1 that P r(Xu = 1) ≥ (it is an inequality becasue u and v may share some neighbors). d(u)+d(v) Since we double counted the edge removals, the average number of edges removed is |
| File Format | |
| Publisher Date | 2013-01-01 |
| Access Restriction | Open |
| Subject Keyword | Simple Analysis Parallel Maximal Independent Set Maximal Matching Algorithm Procedure Mi Inequality Becasue Maximal Independent Set Single Vertex Average Number Tivier Et Simple Parallel Algorithm Luby Algorithm Vertex-induced Subgraph Recursive Call Indicator Variable Xu Edge Removal Assign Unique Priority Return Mi |
| Content Type | Text |
