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

DOI10.1007/978-3-662-55751-8_16MaRDI QIDQ1679971zbMATH OpenOpenAlexFDO

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

Publication date 22 November 2017

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

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)

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.

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

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)