The snow team problem: (Clearing directed subgraphs by mobile agents)

Dariusz Dereniowski , Andrzej Lingas , Mia Persson , Paweł Żyliński

Abstract

We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\cS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\cV_H,\cA_H)$ of $D$ such that (a) $\cS \subseteq \cV_H$, (b) $H$ is the union of $k$ directed walks in $D$, and (c) the underlying graph of $H$ includes a Steiner tree for~$\cS$. We provide several results on parameterized complexity and hardness of the problems.
 Author Dariusz Dereniowski Dariusz Dereniowski,, - , Andrzej Lingas Andrzej Lingas,, - , Mia Persson Mia Persson,, - , Paweł Żyliński II Paweł Żyliński,, - Institute of Informatics Pages 190-203 Publication size in sheets 0.65 Book Klasing Ralf, Zeitoun Marc (eds.): Fundamentals of computation theory: 21st International Symposium, FCT 2017 Bordeaux, France, September 11-13, 2017 : proceedings, no. 10472, 2017, Springer-Verlag , ISBN 978-3-662-55750-1, 453 p. Keywords in English graph searching, FPT-algorithm, NP-hardness, monomial DOI DOI:10.1007/978-3-662-55751-8_16 URL https://link.springer.com/content/pdf/10.1007%2F978-3-662-55751-8.pdf Language en angielski Score (nominal) 5 Score Ministerial score = 5.0, 15-12-2017, BookChapterNotSeriesMainLanguages Citation count* 0
Cite

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back