Brief announcement: Super-fast t-ruling sets
T Bisht, K Kothapalli, S Pemmaraju - … of the 2014 ACM symposium on …, 2014 - dl.acm.org
T Bisht, K Kothapalli, S Pemmaraju
Proceedings of the 2014 ACM symposium on Principles of distributed computing, 2014•dl.acm.orgA t-ruling set of a graph G=(V, E) is a vertex-subset S⊆ V that is independent and satisfies
the property that every vertex v∈ V is at a distance of at most t hops from some vertex in S. A
maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et
al.(FSTTCS 2012) this note presents a randomized algorithm for computing, with high
probability, a t-ruling set in O (t⋅ log1/(t-1) n) rounds for 2< t≤√(log log n) and in (O (√(log
log n))) rounds for t>√(log log n).
the property that every vertex v∈ V is at a distance of at most t hops from some vertex in S. A
maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et
al.(FSTTCS 2012) this note presents a randomized algorithm for computing, with high
probability, a t-ruling set in O (t⋅ log1/(t-1) n) rounds for 2< t≤√(log log n) and in (O (√(log
log n))) rounds for t>√(log log n).
A t-ruling set of a graph G = (V, E) is a vertex-subset S ⊆ V that is independent and satisfies the property that every vertex v ∈ V is at a distance of at most t hops from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et al. (FSTTCS 2012) this note presents a randomized algorithm for computing, with high probability, a t-ruling set in O(t ⋅ log1/(t-1)n) rounds for 2 < t ≤ √(log log n) and in (O(√(log log n))) rounds for t > √(log log n).
ACM Digital Library