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
Pages190-203
Publication size in sheets0.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 Englishgraph searching, FPT-algorithm, NP-hardness, monomial
DOIDOI:10.1007/978-3-662-55751-8_16
URL https://link.springer.com/content/pdf/10.1007%2F978-3-662-55751-8.pdf
Languageen angielski
Score (nominal)5
ScoreMinisterial score = 5.0, 15-12-2017, BookChapterNotSeriesMainLanguages
Citation count*0
Cite
Share Share



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