Patrolling on Dynamic Ring Networks

Das, Shantanu, Di Luna, Giuseppe A and Gasieniec, Leszek A ORCID: 0000-0003-1809-9814 (2019) Patrolling on Dynamic Ring Networks. THEORY AND PRACTICE OF COMPUTER SCIENCE, SOFSEM 2019, 11376. pp. 150-163.

Text 1808.04349v1.pdf - Published version Download (970kB)

Abstract

We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every $I(n)$ time units, with the objective of minimizing the idle time $I(n)$. While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for $k=2$ or $k>2$ agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs.

Item Type:	Article
Uncontrolled Keywords:	cs.DC, cs.DC
Depositing User:	Symplectic Admin
Date Deposited:	29 Aug 2018 09:19
Last Modified:	19 Jan 2023 01:26
DOI:	10.1007/978-3-030-10801-4_13
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3025510