Clearing Connections by Few Agents

Christos Levcopoulos, Andrzej Lingas, Bengt J Nilsson, Pawel Zylinski

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

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.
Original languageEnglish
Title of host publicationFun with Algorithms/Lecture notes in computer science
PublisherSpringer
Pages289-300
Volume8496
ISBN (Print)978-3-319-07890-8
DOIs
Publication statusPublished - 2014
Event7th International Conference on Fun with Algorithms - ITALY
Duration: 2014 Jul 12014 Jul 3

Publication series

Name
Volume8496
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on Fun with Algorithms
Period2014/07/012014/07/03

Subject classification (UKÄ)

  • Medicinal Chemistry

Free keywords

  • clearing paths
  • NP-hardness
  • approximation
  • parametrized complexity

Fingerprint

Dive into the research topics of 'Clearing Connections by Few Agents'. Together they form a unique fingerprint.

Cite this