For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2006/08/01
Online ISSN: 1745-1361
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)>>
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.