Conference proceeding
Brief announcement: Super-fast t-ruling sets
Proceedings of the 2014 ACM symposium on principles of distributed computing, pp.379-381
PODC '14
07/15/2014
DOI: 10.1145/2611462.2611512
Abstract
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 ⋅ log 1/(t-1) n) rounds for 2 < t ≤ √(log log n) and in (O(√(log log n))) rounds for t > √(log log n).
Details
- Title: Subtitle
- Brief announcement: Super-fast t-ruling sets
- Creators
- Tushar Bisht - International Institute of Information Technology, HyderabadKishore Kothapalli - International Institute of Information Technology, HyderabadSriram Pemmaraju - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the 2014 ACM symposium on principles of distributed computing, pp.379-381
- Series
- PODC '14
- DOI
- 10.1145/2611462.2611512
- Publisher
- ACM
- Language
- English
- Date published
- 07/15/2014
- Academic Unit
- Computer Science
- Record Identifier
- 9984259474502771
Metrics
30 Record Views