Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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