On tractability of Cops and Robbers game

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00101200" target="_blank" >RIV/00216208:11320/08:00101200 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On tractability of Cops and Robbers game
Original language description
In this paper we prove that computing the minimum number of cops that can catch a robber in a given graph is NP-hard. Also we show that the parameterized version of the problem is W[2]-hard.
Czech name
O řešitelnosti hry Četníků a Zlodějů
Czech description
Ukazujeme, že určit nejmenší počet četníků, kteří chytnou každého zloděje v daném grafu, je NP-těžké. Dále ukazujeme, že parametrizovaná verze tohoto problému je W[2]-těžká.

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

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

Article name in the collection
Fifth IFIP International Conference on Theoretical Computer Science - TCS 2008
ISBN
978-0-387-09679-7
ISSN
—
e-ISSN
—
Number of pages
15
Pages from-to
—
Publisher name
Springer
Place of publication
New York
Event location
New York
Event date
Jan 1, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000258429400012

Similar results(10)