## Abstract

We prove that a simple distributed algorithm finds a constant approximation of an optimal distance-k dominating set in graphs with no K_{2,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 K_{2,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 language | English (US) |
---|---|

Pages (from-to) | 22-30 |

Number of pages | 9 |

Journal | Theoretical Computer Science |

Volume | 916 |

DOIs | |

State | Published - May 19 2022 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint

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