Maximum vertex occupation time and inert fugitive: recontamination does help

Details Maximum vertex occupation time and inert fugitive: recontamination does help Maximum vertex occupation time and inert fugitive: recontamination does help

2008-02-24

arxiv.org/abs/0802.3512v2

Information Processing Letters 109 (2009) 422-426

Mathematics

Combinatorics

This paper has been withdrawn by the authors [arXiv admin]. The paper has been published and the final journal version has bee

Scientific paper

10.1016/j.ipl.2008.12.022

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.

Affiliated with

Also associated with

No associations

Rating

Maximum vertex occupation time and inert fugitive: recontamination does help does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum vertex occupation time and inert fugitive: recontamination does help, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum vertex occupation time and inert fugitive: recontamination does help will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427212