Clearing directed subgraphs by mobile agents - Publication - Bridge of Knowledge

Search

Clearing directed subgraphs by mobile agents

Abstract

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.

Citations

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Authors (5)

Cite as

Full text

download paper
downloaded 0 times
Publication version
Accepted or Published Version
DOI:
Digital Object Identifier (open in new tab) 10.1016/j.jcss.2018.11.002
License
Copyright (2018 Elsevier Inc)

Keywords

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
JOURNAL OF COMPUTER AND SYSTEM SCIENCES no. 102, pages 57 - 68,
ISSN: 0022-0000
Language:
English
Publication year:
2019
Bibliographic description:
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:
Digital Object Identifier (open in new tab) 10.1016/j.jcss.2018.11.002
Verified by:
Gdańsk University of Technology

seen 87 times

Recommended for you

Meta Tags