The Snow Team Problem
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.
0Web of Science
Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Osula, Paweł Żyliński. (2017). The Snow Team Problem, 10472(Chapter 16), 190-203. https://doi.org/10.1007/978-3-662-55751-8_16
wyświetlono 13 razy