Clearing directed subgraphs by mobile agents Variations on covering with paths

DSpace Repository

Clearing directed subgraphs by mobile agents Variations on covering with paths

Details

Files for download

Find Full text There are no files associated with this item..

Overview of item record
Publication Article, peer reviewed scientific
Title Clearing directed subgraphs by mobile agents Variations on covering with paths
Author Dereniowski, Dariusz ; Lingas, Andrzej ; Osula, Dorota ; Persson, Mia ; Zylinski, Pawel
Date 2019
English 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-H, A(H)) of D such that (a) S subset of V-H, (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. (C) 2018 Elsevier Inc. All rights reserved.
DOI https://doi.org/10.1016/j.jcss.2018.11.002 (link to publisher's fulltext.)
Publisher Elsevier
Host/Issue Journal of Computer and System Sciences;
Volume 102
ISSN 0022-0000
Language eng (iso)
Subject Covering with paths
FPT-algorithm
NP-hardness
Monomial
Technology
Research Subject Categories::TECHNOLOGY
Handle http://hdl.handle.net/2043/30115 Permalink to this page
Facebook

This item appears in the following Collection(s)

Details

Search


Browse

My Account

Statistics