Brief announcement: Super-fast t-ruling sets
Brief announcement: Super-fast t-ruling sets
复制标题
简短公告：超快 T 规则集
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Sriram V. Pemmaraju
中科院分区：
文献类型：
--
作者：
Tushar Bisht;Kishore Kothapalli;Sriram V. Pemmaraju
一个图G =（V，E）的t-规则集是一个独立的顶点子集S ∈ V，它满足这样的性质：每个顶点v ∈ V与S中的某个顶点的距离不超过t跳。极大独立集（MIS）是一个1-规则集。本文扩展了Kothapalli et al.（FSTTCS 2012）的结果，提出了一个随机算法，用于以高概率计算t-规则集，在2 < t ≤ n（log log n）时，时间复杂度为O（t log 1/（t-1）n），在t > n（log log n）时，时间复杂度为O（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).