Catching a Fast Robber on Interval Graphs
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Catching a Fast Robber on Interval Graphs
Popis výsledku v původním jazyce
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
Název v anglickém jazyce
Catching a Fast Robber on Interval Graphs
Popis výsledku anglicky
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
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Lecture Notes in Computer Science
ISSN
0302-9743
e-ISSN
—
Svazek periodika
6648
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
12
Strana od-do
353-364
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—