Maximum vertex occupation time and inert fugitive: recontamination does help

Dariusz Dereniowski
Arxiv ID: 0802.3512Last updated: 3/5/2021
Given a simple graph $G$, we consider the node search problem with inert fugitive. We are interested in minimizing the maximum vertex occupation time, i.e. the maximum number of steps in which a vertex is occupied by a searcher during a search of $G$. We prove that a search program which does not allow a recontamination may not find an optimal solution to this problem, and the difference between the maximum vertex occupation time computed by a monotone search program and a program without such restriction may be arbitrarily large.

PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.

Related papers

Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.