Wyszukiwarka
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
Autorzy (5)
-
Andrzej Lingas
- Lund University Department of Computer Science
-
Mia Persson
- Malmo University Department of Computer Science
-
Paweł Żyliński
- University of Gdańsk Institute of Informatics
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcss.2018.11.002
- Licencja
- Copyright (2018 Elsevier Inc)
Słowa kluczowe
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 90 razy
Publikacje, które mogą cię zainteresować
Bounds on the Cover Time of Parallel Rotor Walks
- D. Dereniowski,
- A. Kosowski,
- D. Pająk
- + 1 autorów