2016/06/23 by Guru Prakash Arumugam, Arumugam, Guru Prakash, John Augustine +9
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Evacuation and Crowd Dynamics #F.2.0 #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1606.07208
openalex publication_date 2016/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Dynamic Graph Network is a graph in which each edge has an associated travel time and a capacity (width) that limits the number of items that can travel in parallel along that edge. Each vertex in this dynamic graph network begins with the number of items that must be evacuated into designated sink vertices. A k-sink evacuation protocol finds the location of k sinks and associated evacuation movement protocol that allows evacuating all the items to a sink in minimum time. The associated evacuation movement must impose a confluent flow, i.e, all items passing through a particular vertex exit that vertex using the same edge. In this paper we address the k-sink evacuation problem on a dynamic path network. We provide solutions that run in O(n log n) time for k=1 and O(k n log2 n) for k >1 and work for arbitrary edge capacities.