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:








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:




Note, Abstract, ©


(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},
ADDRESS = {Málaga, Spain},
MONTH = {July},
ISBN = {3-540-43864-5},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Naveen Sivadasan
Created
04/25/2003 10:17:17 AM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Anja Becker
Anja Becker
Edit Dates
19.04.2004 16:24:52
26.08.2003 15:55:27
26.08.2003 15:54:32
20.06.2003 15:52:37
09.05.2003 14:56:32
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section