Publications Repository - Gdańsk University of Technology

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~$\cS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\cV_H,\cA_H)$ of $D$ such that (a) $\cS \subseteq \cV_H$, (b) $H$ is the union of $k$ directed walks in $D$, and (c) the underlying graph of $H$ includes a Steiner tree for~$\cS$. We provide several results on parameterized complexity and hardness of the problems.

Authors

• prof. dr hab. inż. Dariusz Dereniowski link open in new tab ,
• Andrzej Lingas,
• Mia Persson,
• mgr inż. Dorota Osula link open in new tab ,
• Paweł Żyliński