Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Adler, Micah Räcke, Harald Sivadasan, Naveen Sohler, Christian Vöcking, Berthold dblp dblp dblp dblp dblp Not MPG Author(s): Adler, Micah Räcke, Harald Sohler, Christian
 Editor(s): Widmayer, Peter Triguero, Francisco Morales, Rafael Hennessy, Matthew Eidenbenz, Stephan Conejo, Ricardo dblp dblp dblp dblp dblp dblp Not MPII Editor(s): Widmayer, Peter Triguero, Francisco Morales, Rafael Hennessy, Matthew Eidenbenz, Stephan Conejo, Ricardo
 BibTeX cite key*: NSBV+02

 Title, Booktitle
 Title*: Randomized Pursuit-Evasion in Graphs Booktitle*: Automata, Languages and Programming : 29th International Colloquium, ICALP 2002

 Event, URLs
 URL of the conference: http://sirius.lcc.uma.es/ICALP2002 URL for downloading the paper: http://www.mpi-sb.mpg.de/~sivadasa/papers/evade02.ps Event Address*: Málaga, Spain Language: English Event Date* (no longer used): Organization: European Association for Theoretical Computer Science (EATCS) Event Start Date: 8 July 2002 Event End Date: 13 July 2002

 Publisher
 Name*: Springer URL: http://www.springer.de Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2380 Number: Month: July Pages: 901-912 Year*: 2002 VG Wort Pages: ISBN/ISSN: 3-540-43864-5 Sequence Number: DOI:

 (LaTeX) 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. } Keywords: Algorithms, Games Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{NSBV+02,
AUTHOR = {Adler, Micah and R{\"a}cke, Harald and Sivadasan, Naveen and Sohler, Christian and V{\"o}cking, Berthold},
EDITOR = {Widmayer, Peter and Triguero, Francisco and Morales, Rafael and Hennessy, Matthew and Eidenbenz, Stephan and Conejo, Ricardo},
TITLE = {Randomized Pursuit-Evasion in Graphs},
BOOKTITLE = {Automata, Languages and Programming : 29th International Colloquium, ICALP 2002},
PUBLISHER = {Springer},
YEAR = {2002},
ORGANIZATION = {European Association for Theoretical Computer Science (EATCS)},
VOLUME = {2380},
PAGES = {901--912},
SERIES = {Lecture Notes in Computer Science},