Advanced

Clearing Connections by Few Agents

Levcopoulos, Christos LU ; Lingas, Andrzej LU ; Nilsson, Bengt J LU and Zylinski, Pawel (2014) 7th International Conference on Fun with Algorithms In Fun with Algorithms/Lecture notes in computer science 8496. p.289-300
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
clearing paths, NP-hardness, approximation, parametrized complexity
in
Fun with Algorithms/Lecture notes in computer science
volume
8496
pages
289 - 300
publisher
Springer
conference name
7th International Conference on Fun with Algorithms
external identifiers
  • wos:000342753700025
  • scopus:84903717874
ISSN
0302-9743
1611-3349
ISBN
978-3-319-07890-8
DOI
10.1007/978-3-319-07890-8_25
language
English
LU publication?
yes
id
45b35cb5-f709-4a2d-927f-6b054fda2510 (old id 4800438)
date added to LUP
2014-11-21 09:06:03
date last changed
2017-10-01 03:20:24
@inproceedings{45b35cb5-f709-4a2d-927f-6b054fda2510,
  abstract     = {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.},
  author       = {Levcopoulos, Christos and Lingas, Andrzej and Nilsson, Bengt J and Zylinski, Pawel},
  booktitle    = {Fun with Algorithms/Lecture notes in computer science},
  isbn         = {978-3-319-07890-8},
  issn         = {0302-9743},
  keyword      = {clearing paths,NP-hardness,approximation,parametrized complexity},
  language     = {eng},
  pages        = {289--300},
  publisher    = {Springer},
  title        = {Clearing Connections by Few Agents},
  url          = {http://dx.doi.org/10.1007/978-3-319-07890-8_25},
  volume       = {8496},
  year         = {2014},
}