A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we present a first polynomial time algorithm for the monotone min-max tree partitioning problem and show that the min-max tree partitioning problem is NP-hard if the cost function is not monotone, and that the min-sum tree partitioning problem is NP-hard even if the cost function is monotone. We also consider an evacuation problem in dynamic networks as an application of the tree partitioning problem. The evacuation problem is one of the basic studies on crisis management systems for evacuation guidance of residents against large-scale disasters. We restrict our attention to tree networks and consider flows such that all the supplies going through a common vertex are sent out through a single arc incident to it, since one of the ideal evacuation plans makes everyone to be evacuated fairly and without confusion.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
Fujishige Satoru
Division of Systems Science Department of Systems and Human Science Graduate School of Enginecring S
-
Uno Takeaki
National Institute of Informatics
-
Fujishige Satoru
Kyoto University
-
Uno Takeaki
National Inst. Of Informatics
-
藤重 悟
Kyoto University
-
Mamada Satoko
Osaka University
-
Makino Kazuhisa
Osaka University
関連論文
- BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
- A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
- A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
- A short note on the reducibility of the collapsing knapsack problem
- Practical Techniques for Speeding Up Enumeration Algorithms for Frequent Itemset Mining Problems
- A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
- AN O(n^2 log^2 n) ALGORITHM FOR INPUT-OR-OUTPUT TEST IN DISJUNCTIVE SCHEDULING
- Optimal Sink Location Problem for Dynamic Flows in a Tree Network(Special Section on Discrete Mathematics and Its Applications)
- 劣モジュラ関数最小化のアルゴリズム:ブレイクスルーと周辺の話題 (特集 アルゴリズムの新展開--理論から工学へ)
- ANOTHER SIMPLE PROOF OF THE VALIDITY OF NAGAMOCHI AND IBARAKI'S MIN-CUT ALGORITHM AND QUEYRANNE'S EXTENSION TO SYMMETRIC SUBMODULAR FUNCTION MINIMIZATION
- Generating Chordal Graphs Included in Given Graphs
- PRACTICAL EFFICIENCY OF MAXIMUM FLOW ALGORITHMS USING MA ORDERINGS AND PREFLOWS
- Algorithms for Submodular Flows(Special Issue on Algorithm Engineering : Surveys)
- NEW MAXIMUM FLOW ALGORITHMS BY MA ORDERMGS AND SCALING
- The complexity of free flood filling games (コンピュテーション)
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
- A POLYNOMIAL-TIME ALGORITHM FOR THE GENERALIZED INDEPENDENT-FLOW PROBLEM