The Snow Team Problem - Publikacja - MOST Wiedzy

Wyszukiwarka

The Snow Team Problem

Abstrakt

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~$\cS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\cV_H,\cA_H)$ of $D$ such that (a) $\cS \subseteq \cV_H$, (b) $H$ is the union of $k$ directed walks in $D$, and (c) the underlying graph of $H$ includes a Steiner tree for~$\cS$. We provide several results on parameterized complexity and hardness of the problems.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Informacje szczegółowe

Kategoria:
Archiwalna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
Fundamentals of Computation Theory strony 190 - 203
Język:
angielski
Rok wydania:
2017
Opis bibliograficzny:
Dereniowski D., Lingas A., Persson M., Urbańska D., Żyliński P.: The Snow Team Problem// Fundamentals of Computation Theory/ Berlin, Heidelberg: Springer, 2017, s.190-203
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-662-55751-8_16

wyświetlono 14 razy

Publikacje, które mogą cię zainteresować

Bounds on the Cover Time of Parallel Rotor Walks

2014

Fast Collaborative Graph Exploration

2013

Fast collaborative graph exploration

2015
Meta Tagi