The Snow Team ProblemShow others and affiliations
2017 (English)In: Fundamentals of Computation Theory: 21st International Symposium, FCT 2017, Bordeaux, France, September 11–13, 2017, Proceedings / [ed] Ralf Klasing; Marc Zeitoun, Springer, 2017, p. 190-203Conference paper, Published paper (Refereed)
Abstract [en]
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 � of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph �=(��,��) of D such that (a) �⊆��, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for �. We provide several results on parameterized complexity and hardness of the problems.
Place, publisher, year, edition, pages
Springer, 2017. p. 190-203
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10472
Keywords [en]
Graph searching; FPT-algorithm; NP-hardness; Monomial
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mau:diva-64415DOI: 10.1007/978-3-662-55751-8_16ISI: 000717257400016Scopus ID: 2-s2.0-85029431842ISBN: 978-3-662-55750-1 (print)ISBN: 978-3-662-55751-8 (electronic)OAI: oai:DiVA.org:mau-64415DiVA, id: diva2:1819460
Conference
21st International Symposium, FCT 2017, Bordeaux, France, September 11–13, 2017
2023-12-142023-12-142023-12-14Bibliographically approved