Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
FPT-algorithm, Graph searching, Monomial, NP-hardness
host publication
Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings
series title
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
conference name
21th International Symposium on Fundamentals of Computation Theory, FCT 2017
conference location
Bordeaux, France
conference dates
2017-09-11 - 2017-09-13
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
2024-02-29 22:58:07
@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         = {{03029743}},
  keywords     = {{FPT-algorithm; Graph searching; Monomial; NP-hardness}},
  language     = {{eng}},
  pages        = {{190--203}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
  title        = {{The snow team problem : (Clearing Directed subgraphs by mobile agents)}},
  url          = {{http://dx.doi.org/10.1007/978-3-662-55751-8_16}},
  doi          = {{10.1007/978-3-662-55751-8_16}},
  volume       = {{10472 LNCS}},
  year         = {{2017}},
}