Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Snow Team Problem
Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 80-233, Gdańsk, Poland.
Department of Computer Science, Lund University, 221 00, Lund, Sweden.
Malmö högskola, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 80-233, Gdańsk, Poland.
Show 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
Available from: 2023-12-14 Created: 2023-12-14 Last updated: 2023-12-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Persson, Mia

Search in DiVA

By author/editor
Persson, Mia
By organisation
Department of Computer Science and Media Technology (DVMT)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf