Cops and Robbers on String Graphs
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Cops and Robbers on String Graphs
Original language description
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
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 26th International Symposium on Algorithms and Computation
ISBN
978-3-662-48970-3
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
355-366
Publisher name
Springer Berlin Heidelberg
Place of publication
Berlin
Event location
Nagoya, Japonsko
Event date
Dec 9, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—