patternMinor
Independent set where two vertices need to have distance >= c
Viewed 0 times
independentneedhavewheredistancetwoverticesset
Problem
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?
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?
Solution
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
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
Context
StackExchange Computer Science Q#11129, answer score: 7
Revisions (0)
No revisions yet.