de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
 
 
DownloadE-Mail
  Randomized Pursuit-Evasion in Graphs

Adler, M., Räcke, H., Sivadasan, N., Sohler, C., & Vöcking, B. (2002). Randomized Pursuit-Evasion in Graphs. In Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 (pp. 901-912). Berlin, Germany: Springer.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-000F-304A-E Version Permalink: http://hdl.handle.net/11858/00-001M-0000-000F-304D-8
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Adler, Micah, Author
Räcke, Harald, Author
Sivadasan, Naveen1, Author              
Sohler, Christian, Author
Vöcking, Berthold1, Author              
Widmayer, Peter, Editor
Triguero, Francisco, Editor
Morales, Rafael, Editor
Hennessy, Matthew, Editor
Eidenbenz, Stephan, Editor
Conejo, Ricardo, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019              

Content

show
hide
Free keywords: -
 Abstract: { We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is played in rounds and in each round both the hunter and the rabbit are located at a node of the graph. Between rounds both the hunter and the rabbit can stay at the current node or move to another node. The hunter is assumed to be {\em restricted} to the graph $G$: in every round, the hunter can move using at most one edge. For the rabbit we investigate two models: in one model the rabbit is restricted to the same graph as the hunter, and in the other model the rabbit is {\em unrestricted}, i.e., it can jump to an arbitrary node in every round. We say that the rabbit is {\em caught}\/ as soon as hunter and rabbit are located at the same node in a round. The goal of the hunter is to catch the rabbit in as few rounds as possible, whereas the rabbit aims to maximize the number of rounds until it is caught. Given a randomized hunter strategy for $G$, the {\em escape length} for that strategy is the worst case expected number of rounds it takes the hunter to catch the rabbit, where the worst case is with regards to all (possibly randomized) rabbit strategies. Our main result is a hunter strategy for general graphs with an escape length of only $\O(n \log (\diam(G)))$ against restricted as well as unrestricted rabbits. This bound is close to optimal since $\Omega(n)$ is a trivial lower bound on the escape length in both models. Furthermore, we prove that our upper bound is optimal up to constant factors against unrestricted rabbits. }

Details

show
hide
Language(s): eng - English
 Dates: 2003-08-262002
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: eDoc: 202057
Other: Local-ID: C1256428004B93B8-07C33A9C6FA1B038C1256D13002D8771-NSBV+02
 Degree: -

Event

show
hide
Title: ICALP 2002
Place of Event: Málaga, Spain
Start-/End Date: 2002-07-08 - 2002-07-13

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, Languages and Programming : 29th International Colloquium, ICALP 2002
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 901 - 912 Identifier: ISBN: 3-540-43864-5

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2380 Sequence Number: - Start / End Page: - Identifier: -