Problem Detail: An independent set (IS) in a graph is a set $V’ subseteq V(G)$ of pairwise non-adjacent vertices. I am interested in the generalization $c$-IS where two nodes in $V’ subseteq V(G)$ need to have distance at least $c$ to any other vertex in $V’$. Has this problem been studied before?
Asked By : user695652
Answered By : Peter
Yes, this is called ruling set. An $(alpha,beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $alpha$ from each other, and, for any node $v notin S$, there exists a node $u in S$ such that the distance between $u$ and $v$ is at most $beta$. So a maximal independent set is a $(2,1)$-ruling set. (This is defined in [1] but there might be prior references.) [1] Korman et al. Toward more localized local algorithms: removing assumptions concerning global knowledge. PODC ’11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing Pages 49-58
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11129 Ask a Question Download Related Notes/Documents
