TY - JOUR
T1 - Distributed distance domination in graphs with no K2,t-minor
AU - Czygrinow, Andrzej
AU - Hanćkowiak, Michał
AU - Witkowski, Marcin
N1 - Funding Information:
Research supported in part by Simons Foundation Grant # 521777.
Publisher Copyright:
© 2022 Elsevier B.V.
PY - 2022/5/19
Y1 - 2022/5/19
N2 - We prove that a simple distributed algorithm finds a constant approximation of an optimal distance-k dominating set in graphs with no K2,t-minor. The algorithm runs in a constant number of rounds. We further show how this procedure can be used to give a distributed algorithm which given ϵ>0 and k,t∈Z+ finds in a graph G=(V,E) with no K2,t-minor a distance-k dominating set of size at most (1+ϵ) of the optimum. The algorithm runs in O(log⁎|V|) rounds in the Local model. In particular, both algorithms work in outerplanar graphs.
AB - We prove that a simple distributed algorithm finds a constant approximation of an optimal distance-k dominating set in graphs with no K2,t-minor. The algorithm runs in a constant number of rounds. We further show how this procedure can be used to give a distributed algorithm which given ϵ>0 and k,t∈Z+ finds in a graph G=(V,E) with no K2,t-minor a distance-k dominating set of size at most (1+ϵ) of the optimum. The algorithm runs in O(log⁎|V|) rounds in the Local model. In particular, both algorithms work in outerplanar graphs.
KW - Distance dominating set
KW - Distributed algorithms
KW - Local model
KW - Sparse graphs
UR - http://www.scopus.com/inward/record.url?scp=85127305217&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85127305217&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2022.03.001
DO - 10.1016/j.tcs.2022.03.001
M3 - Article
AN - SCOPUS:85127305217
SN - 0304-3975
VL - 916
SP - 22
EP - 30
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -