Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Clearing Connections by Few Agents

In English

Författare

Summary, in English

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.

Avdelning/ar

Publiceringsår

2014

Språk

Engelska

Sidor

289-300

Publikation/Tidskrift/Serie

Fun with Algorithms/Lecture notes in computer science

Volym

8496

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Medicinal Chemistry

Nyckelord

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

Conference name

7th International Conference on Fun with Algorithms

Conference date

2014-07-01 - 2014-07-03

Status

Published

Forskningsgrupp

  • Clinical Chemistry, Malmö

ISBN/ISSN/Övrigt

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-319-07890-8