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

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja monograficzna
Typ:
rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
Tytuł wydania:
Fundamentals of Computation Theory strony 190 - 203
Język:
angielski
Rok wydania:
2017
Opis bibliograficzny:
Dereniowski D., Lingas A., Persson M., Osula D., Żyliński P.: The Snow Team Problem// / 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
Weryfikacja:
Politechnika Gdańska

wyświetlono 129 razy

Publikacje, które mogą cię zainteresować

Meta Tagi