TY - GEN
T1 - Clearing Connections by Few Agents
AU - Levcopoulos, Christos
AU - Lingas, Andrzej
AU - Nilsson, Bengt J
AU - Zylinski, Pawel
PY - 2014
Y1 - 2014
N2 - We study the problem of clearing connections by agents placed at some vertices in a directed graph. The agents can move only along directed paths. The objective is to minimize the number of agents guaranteeing that any pair of vertices can be connected by a underlying undirected path that can be cleared by the agents. We provide several results on the hardness, approximability and parameterized complexity of the problem. In particular, we show it to be: NP-hard, 2-approximable in polynomial-time, and solvable exactly in O(alpha n(3)2(2 alpha)) time, where a is the number of agents in the solution. In addition, we give a simple linear-time algorithm optimally solving the problem in digraphs whose underlying graphs are trees. Finally, we discuss a related problem, where the task is to clear with a minimum number of agents a subgraph of the underlying graph containing its spanning tree. We show that this problem also admits a 2-approximation in polynomial time.
AB - We study the problem of clearing connections by agents placed at some vertices in a directed graph. The agents can move only along directed paths. The objective is to minimize the number of agents guaranteeing that any pair of vertices can be connected by a underlying undirected path that can be cleared by the agents. We provide several results on the hardness, approximability and parameterized complexity of the problem. In particular, we show it to be: NP-hard, 2-approximable in polynomial-time, and solvable exactly in O(alpha n(3)2(2 alpha)) time, where a is the number of agents in the solution. In addition, we give a simple linear-time algorithm optimally solving the problem in digraphs whose underlying graphs are trees. Finally, we discuss a related problem, where the task is to clear with a minimum number of agents a subgraph of the underlying graph containing its spanning tree. We show that this problem also admits a 2-approximation in polynomial time.
KW - clearing paths
KW - NP-hardness
KW - approximation
KW - parametrized complexity
U2 - 10.1007/978-3-319-07890-8_25
DO - 10.1007/978-3-319-07890-8_25
M3 - Paper in conference proceeding
SN - 978-3-319-07890-8
VL - 8496
SP - 289
EP - 300
BT - Fun with Algorithms/Lecture notes in computer science
PB - Springer
T2 - 7th International Conference on Fun with Algorithms
Y2 - 1 July 2014 through 3 July 2014
ER -