The snow team problem : (Clearing Directed subgraphs by mobile agents)
(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:
https://lup.lub.lu.se/record/8aa5da00-9edd-4f20-bddf-dc47eb55efc7
- author
- Dereniowski, Dariusz ; Lingas, Andrzej LU ; Persson, Mia LU ; Urbańska, Dorota and Żyliński, Paweł
- organization
- publishing date
- 2017
- 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
- 2025-01-07 21:49:57
@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}}, }