Distributed distance domination in graphs with no K2,t-minor

Andrzej Czygrinow, Michał Hanćkowiak, Marcin Witkowski

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)22-30
Number of pages9
JournalTheoretical Computer Science
Volume916
DOIs
StatePublished - May 19 2022

Keywords

  • Distance dominating set
  • Distributed algorithms
  • Local model
  • Sparse graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Distributed distance domination in graphs with no K2,t-minor'. Together they form a unique fingerprint.

Cite this