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 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 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
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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
03029743
16113349
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    = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
  isbn         = {9783662557501},
  issn         = {03029743},
  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},
}