Clearing Connections by Few Agents
(2014) 7th International Conference on Fun with Algorithms 8496. p.289300 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: NPhard, 2approximable in polynomialtime, 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 lineartime 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: NPhard, 2approximable in polynomialtime, 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 lineartime 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 2approximation in polynomial time. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/4800438
 author
 Levcopoulos, Christos ^{LU} ; Lingas, Andrzej ^{LU} ; Nilsson, Bengt J ^{LU} and Zylinski, Pawel
 organization
 publishing date
 2014
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 clearing paths, NPhardness, approximation, parametrized complexity
 host publication
 Fun with Algorithms/Lecture notes in computer science
 volume
 8496
 pages
 289  300
 publisher
 Springer
 conference name
 7th International Conference on Fun with Algorithms
 conference location
 ITALY
 conference dates
 20140701  20140703
 external identifiers

 wos:000342753700025
 scopus:84903717874
 ISSN
 03029743
 16113349
 ISBN
 9783319078908
 DOI
 10.1007/9783319078908_25
 language
 English
 LU publication?
 yes
 id
 45b35cb5f7094a2d927f6b054fda2510 (old id 4800438)
 date added to LUP
 20141121 09:06:03
 date last changed
 20190106 04:31:41
@inproceedings{45b35cb5f7094a2d927f6b054fda2510, 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: NPhard, 2approximable in polynomialtime, 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 lineartime 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 2approximation in polynomial time.}, author = {Levcopoulos, Christos and Lingas, Andrzej and Nilsson, Bengt J and Zylinski, Pawel}, isbn = {9783319078908}, issn = {03029743}, keyword = {clearing paths,NPhardness,approximation,parametrized complexity}, language = {eng}, location = {ITALY}, pages = {289300}, publisher = {Springer}, title = {Clearing Connections by Few Agents}, url = {http://dx.doi.org/10.1007/9783319078908_25}, volume = {8496}, year = {2014}, }