Opening book details…
Can I read Parameterized Pursuit-evasion Games on EtoBox?
Parameterized Pursuit-evasion Games by Allan Scott; Ulrike Stege is a Computer Science article available to read on EtoBox.
What is Parameterized Pursuit-evasion Games about?
We study the parameterized complexity of four variants of pursuit-evasion on graphs: Seeded Pursuit Evasion, Short Seeded Pursuit Evasion, Directed Pursuit Evasion and Short Directed Pursuit Evasion. Both Seeded Pursuit Evasion and Short Seeded Pursuit Evasion are played on undirected graphs with given starting positions for both the cops and the robber. Directed Pursuit Evasion and its short variant are played on directed graphs, with the players free to choose their starting positions. We show for Seeded Pursuit Evasion and Directed Pursuit Evasion that finding a winning strategy for the cops is AW[\*]-hard when we parameterize by the number of cops. Further, we show that the short (k-move) variants of these problems (Short Seeded Pursuit Evasion and Short Directed Pursuit Evasion) are AW[\*]-complete when we parameterize by both the number of cops and turns.
Who reads Parameterized Pursuit-evasion Games?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Allan Scott; Ulrike Stege
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)
- Published
- 2010
- Language
- EN
- Field
- Computer Science (Physical Sciences)