Catching a Fast Robber on Interval Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10104228" target="_blank" >RIV/00216208:11320/11:10104228 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-642-20877-5_35" target="_blank" >http://dx.doi.org/10.1007/978-3-642-20877-5_35</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-20877-5_35" target="_blank" >10.1007/978-3-642-20877-5_35</a>

Result language

angličtina

Original language name

Catching a Fast Robber on Interval Graphs

Original language description

We analyse the Cops and oo-fast Robber game on the class of interval graphs and show it to be polynomially decidable on such graphs. This solves an open problem posed in paper "Pursuing a fast robber on a graph" by Fomin et al. [4] The game is known to be already NP-hard on chordal graphs and split-graphs. The game is played by two players, one controlling k cops, the other a robber. The players alternate in turns, all the cops move at once to distance at most one, the robber moves along any cop-free path. Cops win by capturing the robber, the robber by avoiding capture. The analysis relies on the properties of an interval representation of the graph. We show that while the game-state graph is generally exponential, every cops'' move can be decomposedinto simple moves of three types, and the states are reduced to those defined by certain cuts of the interval representation. This gives a restricted game equivalent to the original one together with a winning strategy computable in polyn

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2011

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Volume of the periodical

6648

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

12

Pages from-to

353-364

UT code for WoS article

—

EID of the result in the Scopus database

—