The snow team problem: (Clearing directed subgraphs by mobile agents)
Dariusz Dereniowski , Andrzej Lingas , Mia Persson , Paweł Żyliński
AbstractWe 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.
|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|
|Score||= 5.0, 15-12-2017, BookChapterNotSeriesMainLanguages|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.