# Run for Cover: Dominating Set via Mobile Agents

arXiv: https://arxiv.org/abs/2309.02200 · HTML: https://mlsanity.com/paper/2309.02200/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2023.

## Built on by (most cited first, 2 of 2)

- [Computing Tree Structures in Anonymous Graphs via Mobile Agents](https://mlsanity.com/paper/2506.19365/) (2025)
- [Agentic Distributed Computing](https://mlsanity.com/paper/2507.04459/) (2025)

## Abstract (arXiv)

Research involving computing with mobile agents is a fast-growing field, given the advancement of technology in automated systems, e.g., robots, drones, self-driving cars, etc. Therefore, it is pressing to focus on solving classical network problems using mobile agents. In this paper, we study one such problem -- finding small dominating sets of a graph G using mobile agents. Dominating set is interesting in the field of mobile agents as it opens up a way for solving various robotic problems, e.g., guarding, covering, facility location, transport routing, etc. In this paper, we first present two algorithms for computing a em minimal dominating set: (i) an O(m) time algorithm if the robots start from a single node (i.e., gathered initially), (ii) an O(ℓDeltalog(λ)+nℓ+m) time algorithm, if the robots start from multiple nodes (i.e., positioned arbitrarily), where m is the number of edges and Delta is the maximum degree of G, ℓ is the number of clusters of the robot initially and λ is the maximum ID-length of the robots. Then we present a ln (Delta) approximation algorithm for the em minimum dominating set which takes O(nDeltalog (λ)) rounds.