An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity(<Special Section>Invited Papers from New Horizons in Computing)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2006-08-01
著者
-
KAMIYAMA Naoyuki
Department of Information and System Engineering, Faculty of Science and Engineering, Chuo Universit
-
Katoh Naoki
Graduate School Of Kyoto University
-
Katoh Naoki
Department Of Architecture And Architectural Engineering Kyoto University
-
Kamiyama Naoyuki
Department Of Information And System Engineering Chuo University
-
Kamiyama Naoyuki
Department Of Architecture And Architectural Engineering Kyoto University
-
Takizawa Atsushi
Department Of Architecture And Architectural Engineering Kyoto University
-
Katoh Naoki
Department of Architecture and Architectural Engineering, Kyoto University
関連論文
- Improved Approximation Algorithms for Firefighter Problem on Trees
- DS-1-7 無交差ラーマンフレームワーク列挙アルゴリズム(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- The Bacteriology of Acne Vulgaris and Antimicrobial Susceptibility of Propionibacterium acnes and Staphylococcus epidermidis Isolated from Acne Lesions
- 1B2 The Multicover Problem in Graphs arising from Patrol Route Planning
- An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity(Invited Papers from New Horizons in Computing)
- Inserting Points Uniformly at Every Instance
- Computational Complexities of University Interview Timetabling
- Multi-Objective Optimization of Spatial Truss Structures by Genetic Algorithm
- AN EFFICIENT ALGORITHM FOR BICRITERIA MINIMUM-COST CIRCULATION PROBLEM
- Finding a Triangular Mesh with a Constant Number of Different Edge Lengths(Invited Papers from New Horizons in Computing)
- AN ε-APPROXIMATION SCHEME FOR MINIMUM VARIANCE PROBLEMS
- Online Vertex Exploration Problems in a Simple Polygon