An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity

Naoyuki KAMIYAMA  Naoki KATOH  Atsushi TAKIZAWA  

IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.8   pp.2372-2379
Publication Date: 2006/08/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.8.2372
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
dynamic network flow,  evacuation problem,  quickest flow problem,  

Full Text: PDF(316KB)>>
Buy this Article

In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.