Advanced

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

Dereniowski, Dariusz; Lingas, Andrzej LU ; Persson, Mia LU ; Urbańska, Dorota and Żyliński, Paweł (2017) 21th International Symposium on Fundamentals of Computation Theory, FCT 2017 In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings 10472 LNCS. p.190-203
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 S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H = (VH, AH) of D such that (a) S ⊆ VH, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S. We provide several results on parameterized complexity and hardness of the problems.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
FPT-algorithm, Graph searching, Monomial, NP-hardness
in
Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings
volume
10472 LNCS
pages
14 pages
publisher
Springer Verlag
conference name
21th International Symposium on Fundamentals of Computation Theory, FCT 2017
external identifiers
  • scopus:85029431842
ISSN
16113349
03029743
ISBN
9783662557501
DOI
10.1007/978-3-662-55751-8_16
language
English
LU publication?
yes
id
8aa5da00-9edd-4f20-bddf-dc47eb55efc7
date added to LUP
2017-10-04 09:22:36
date last changed
2018-01-07 12:20:30
@inproceedings{8aa5da00-9edd-4f20-bddf-dc47eb55efc7,
  abstract     = {<p>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 S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H = (V<sub>H</sub>, A<sub>H</sub>) of D such that (a) S ⊆ V<sub>H</sub>, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S. We provide several results on parameterized complexity and hardness of the problems.</p>},
  author       = {Dereniowski, Dariusz and Lingas, Andrzej and Persson, Mia and Urbańska, Dorota and Żyliński, Paweł},
  booktitle    = {Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings},
  isbn         = {9783662557501},
  issn         = {16113349},
  keyword      = {FPT-algorithm,Graph searching,Monomial,NP-hardness},
  language     = {eng},
  pages        = {190--203},
  publisher    = {Springer Verlag},
  title        = {The snow team problem : (Clearing Directed subgraphs by mobile agents)},
  url          = {http://dx.doi.org/10.1007/978-3-662-55751-8_16},
  volume       = {10472 LNCS},
  year         = {2017},
}