Fence patrolling by mobile agents with distinct speeds

Akitoshi Kawamura, Yusuke Kobayashi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Citations (Scopus)


Suppose we want to patrol a fence (line segment) using k mobile agents with speeds v1, . . . , vk so that every point on the fence is visited by an agent at least once in every unit time period. Czyzowicz et al. conjectured that the maximum length of the fence that can be patrolled is (v1 + ··· + vk)/2, which is achieved by the simple strategy where each agent i moves back and forth in a segment of length vi/2. We disprove this conjecture by a counterexample involving k = 6 agents. We also show that the conjecture is true for k ≤ 3.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783642352607
Publication statusPublished - 2012
Event23rd International Symposium on Algorithms and Computation, ISAAC 2012 - Taipei, Taiwan, Province of China
Duration: Dec 19 2012Dec 21 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7676 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other23rd International Symposium on Algorithms and Computation, ISAAC 2012
Country/TerritoryTaiwan, Province of China

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Fence patrolling by mobile agents with distinct speeds'. Together they form a unique fingerprint.

Cite this