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

Abstract

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.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Authors (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

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:

Articles

Type:

artykuły w czasopismach

Published in:

THEORETICAL COMPUTER SCIENCE no. 1035,
ISSN: 0304-3975

Language:

English

Publication year:

2025

Bibliographic description:

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

DOI: