Clearing directed subgraphs by mobile agents - Publikacja - MOST Wiedzy

Wyszukiwarka

Clearing directed subgraphs by mobile agents

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 S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. Since a directed walk is a not necessarily a simple directed path, the problem is actually on covering with paths. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem. Our main fixed-parameter algorithm is randomized.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
JOURNAL OF COMPUTER AND SYSTEM SCIENCES nr 102, strony 57 - 68,
ISSN: 0022-0000
Język:
angielski
Rok wydania:
2019
Opis bibliograficzny:
Dereniowski D., Lingas A., Osula D., Persson M., Żyliński P.: Clearing directed subgraphs by mobile agents// JOURNAL OF COMPUTER AND SYSTEM SCIENCES. -Vol. 102, (2019), s.57-68
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcss.2018.11.002
Weryfikacja:
Politechnika Gdańska

wyświetlono 6 razy

Publikacje, które mogą cię zainteresować

Meta Tagi