Optimal Sink Location Problem for Dynamic Flows in a Tree Network(Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n^2 ) time algorithm for the sink location problem, where n is the number of vertices in the network.
- 社団法人電子情報通信学会の論文
- 2002-05-01
著者
-
Fujishige Satoru
Division of Systems Science Department of Systems and Human Science Graduate School of Enginecring S
-
藤重 悟
Kyoto University
-
Mamada Satoko
Osaka University
-
Makino Kazuhisa
Osaka University
-
MAMADA Satoko
The authors are with Division of Systems Science, Graduate School of Engineering Science, Osaka Univ
-
MAKINO kazuhisa
The authors are with Division of Systems Science, Graduate School of Engineering Science, Osaka Univ
-
FUJISHIGE Satoru
The authors are with Division of Systems Science, Graduate School of Engineering Science, Osaka Univ
関連論文
- 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 TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
- 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
- Algorithms for Submodular Flows(Special Issue on Algorithm Engineering : Surveys)