Discrete evacuation in graphs with multiple exits

Piotr Borowiecki; Shantanu Das; Dariusz Dereniowski; Łukasz Kuszner

doi:10.1016/j.tcs.2025.115141

Discrete evacuation in graphs with multiple exits

Abstrakt

In this paper, we consider the problem of efficient evacuation of mobile agents from distinct nodes in a graph to multiple exit nodes, while avoiding congestion and bottlenecks, and minimizing the total evacuation time. Each node in the graph can only hold one agent at a time, so the agents must choose their movements based on the locations of other agents to optimize the evacuation process. We consider two scenarios: the centralized (offline) and the distributed (online) setting. In the former one, the agents have complete information about the initial positions of other agents. In the distributed setting, agents lack prior knowledge of other agents' locations but can communicate locally with nearby agents and must adapt their strategy in an online fashion as they move and gather more information. In this study, we propose an offline polynomial time solution for determining the optimal evacuation strategy for all agents. In the online case, where agents can communicate at a distance of two in the graph, a constant-competitive algorithm is presented. Additionally, we demonstrate that when agents are heterogeneous and each type of agent can access only a certain subgraph of the original graph, computing the optimal strategy becomes NP-hard, even with full global knowledge. This result remains true even if there are only two types of agents or, even if the optimal evacuation time is a small constant.

Cytowania

0

CrossRef
0

Web of Science
0

Scopus

Autorzy (4)

Piotr Borowiecki
- Institute of Control and Computation Engineering, University of Zielona Góra
Shantanu Das
- Aix Marseille Univ, Université de Toulon, CNRS, LIS
Dariusz Dereniowski prof. dr hab. inż.
Łukasz Kuszner dr inż.
- Institute of Informatics, University of Gdańsk

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:

Publikacja w czasopiśmie

Typ:

artykuły w czasopismach

Opublikowano w:

THEORETICAL COMPUTER SCIENCE nr 1035,
ISSN: 0304-3975

Język:

angielski

Rok wydania:

2025

Opis bibliograficzny:

Borowiecki P., Das S., Dereniowski D., Kuszner Ł.: Discrete evacuation in graphs with multiple exits// THEORETICAL COMPUTER SCIENCE -Vol. 1035, (2025), s.115141-

DOI: