A Timecop's Work Is Harder Than You Think

Autor: Morawietz, Nils, Rehs, Carolin, Weller, Mathias

Publikováno v: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Aug 2020, Prague, Czech Republic. pp.71:1--71:14, ⟨10.4230/LIPIcs.MFCS.2020.71⟩

International audience; We consider the (parameterized) complexity of a cop and robber game on periodic, temporal graphs and a problem on periodic sequences to which these games relate intimately. In particular, we show that it is NP-hard to decide (

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::85a122aa3fbfa522542bd99459514eda
https://hal.archives-ouvertes.fr/hal-03004095