Clearing directed subgraphs by mobile agents: variations on covering with paths

Dariusz Dereniowski , Andrzej Lingas , Dorota Osula , Mia Persson , Paweł Żyliński

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⊆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.
Autor Dariusz Dereniowski
Dariusz Dereniowski
-
, Andrzej Lingas
Andrzej Lingas
-
, Dorota Osula
Dorota Osula
-
, Mia Persson
Mia Persson
-
, Paweł Żyliński (WMFiI / II)
Paweł Żyliński
- Instytut Informatyki
Tytuł czasopisma/seriiJournal of Computer and System Sciences, ISSN 0022-0000, (A 30 pkt)
Rok wydania2019
Tom102
Paginacja57-68
Objętość publikacji w arkuszach wydawniczych0.55
Słowa kluczowe w języku angielskimcovering with paths, FPT-algorithm, NP-hardness, monomial
Klasyfikacja ASJC2604 Applied Mathematics; 1703 Computational Theory and Mathematics; 1705 Computer Networks and Communications; 2614 Theoretical Computer Science
DOIDOI:10.1016/j.jcss.2018.11.002
URL https://doi.org/10.1016/j.jcss.2018.11.002
Języken angielski
Punktacja (całkowita)30
PunktacjaPunktacja MNiSW = 30.0, 24-07-2019, ArticleFromJournal
Wskaźniki publikacji Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.768; Impact Factor WoS: 2017 = 1.497 (2) - 2017=1.914 (5)
Liczba cytowań*
Cytuj
Udostępnij Udostępnij

Pobierz odnośnik do tego rekordu


* Podana liczba cytowań wynika z analizy informacji dostępnych w Internecie i jest zbliżona do wartości obliczanej przy pomocy systemu Publish or Perish.
Powrót