Cops and Robbers on String Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10316177" target="_blank" >RIV/00216208:11320/15:10316177 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007%2F978-3-662-48971-0_31" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-662-48971-0_31</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-48971-0_31" target="_blank" >10.1007/978-3-662-48971-0_31</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Cops and Robbers on String Graphs

Popis výsledku v původním jazyce

The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph. One controls k cops and the other a robber. The players alternate and move their pieces to the distance at most one. The cops win if they capture the robber, the robber wins by escaping indefinitely. The cop number of G is the smallest k such that k cops win the game. We extend the results of Gavenčiak et al. [ISAAC 2013], investigating the maximum cop number of geometric intersection graphs.Our main result shows that the maximum cop number of string graphs is at most 15, improving the previous bound 30. We generalize this approach to string graphs on a surface of genus g to show that the maximum cop number is at most 10g+15, which strengthens the result of Quilliot [J. Combin. Theory Ser. B 38, 89-92 (1985)]. For outer string graphs, we show that the maximum cop number is between 3 and 4. Our results also imply polynomial-time algorithms determining the cop number for all t

Název v anglickém jazyce

Cops and Robbers on String Graphs

Popis výsledku anglicky

The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph. One controls k cops and the other a robber. The players alternate and move their pieces to the distance at most one. The cops win if they capture the robber, the robber wins by escaping indefinitely. The cop number of G is the smallest k such that k cops win the game. We extend the results of Gavenčiak et al. [ISAAC 2013], investigating the maximum cop number of geometric intersection graphs.Our main result shows that the maximum cop number of string graphs is at most 15, improving the previous bound 30. We generalize this approach to string graphs on a surface of genus g to show that the maximum cop number is at most 10g+15, which strengthens the result of Quilliot [J. Combin. Theory Ser. B 38, 89-92 (1985)]. For outer string graphs, we show that the maximum cop number is between 3 and 4. Our results also imply polynomial-time algorithms determining the cop number for all t

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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ů

Název statě ve sborníku

Proceedings of the 26th International Symposium on Algorithms and Computation

ISBN

978-3-662-48970-3

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

355-366

Název nakladatele

Springer Berlin Heidelberg

Místo vydání

Berlin

Místo konání akce

Nagoya, Japonsko

Datum konání akce

9. 12. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—