Search
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.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (5)
-
Andrzej Lingas
-
Mia Persson
-
Paweł Żyliński
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Monographic publication
- Type:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Title of issue:
- Fundamentals of Computation Theory strony 190 - 203
- Language:
- English
- Publication year:
- 2017
- Bibliographic description:
- Dereniowski D., Lingas A., Persson M., Osula D., Żyliński P.: The Snow Team Problem// / Berlin, Heidelberg: Springer, 2017, s.190-203
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/978-3-662-55751-8_16
- Verified by:
- Gdańsk University of Technology
seen 78 times
Recommended for you
Bounds on the Cover Time of Parallel Rotor Walks
- D. Dereniowski,
- A. Kosowski,
- D. Pająk
- + 1 authors
2014