The snow team problem (clearing directed subgraphs by mobile agents)

DOI10.1007/978-3-662-55751-8_16zbMATH Open1495.68165arXiv1712.00316OpenAlexW2912246957MaRDI QIDQ1679971FDOQ1679971

Authors: Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbańska, Paweł Żyliński 

Publication date: 22 November 2017

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~$mathcalS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(mathcal{V}_H,mathcal{A}_H)$ of $D$ such that (a) $mathcalSsubseteqmathcal{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 $mathcalS$ in $D$. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem.

Full work available at URL: https://arxiv.org/abs/1712.00316

Recommendations

• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• Integer programming models and algorithms for the graph decontamination problem with mobile agents
• Rendezvous of mobile agents in directed graphs
• scientific article; zbMATH DE number 3928685
• Decontaminating arbitrary graphs by mobile agents: a survey
• Solving multi-agent path finding on strongly biconnected digraphs
• A branch-and-cut algorithm for the team orienteering problem
• A Branch-and-Cut Algorithm for Solving the Team Orienteering Problem
• An exact algorithm for team orienteering problems

zbMATH Keywords

monomialNP-hardnessgraph searchingFPT-algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (1)

• Clearing directed subgraphs by mobile agents. Variations on covering with paths

This page was built for publication: The snow team problem (clearing directed subgraphs by mobile agents)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679971)