紧急网络中的最小饱和流问题(英文)  

The Minimum Saturated Flow Problem in Emergency Networks

作　　者：林诒勋[1] 李湘露[1] 邓俊强[1] 

机构地区：[1]郑州大学数学系,郑州450052

出　　处：《运筹学学报》2001年第2期12-20,共9页Operations Research Transactions

基　　金：Project supported by the National Natural Science Foundation of China (10071076)

摘　　要：网络Ｎ中的一个流，如果沿前向已无法再增流，则称为饱和流．在交通拥挤或紧急疏散时，网络往往被一饱和流所堵塞．显然，这饱和流的值越小，网络的性能就越差．于是从网络分析的观点就提出最小饱和流问题．本文首先证明此问题是ＮＰ-困难的，然后给出关于最小饱和流与最大流的关系及算法方面的结果．A flow in network N is said to be saturated if its value cannot be enhanced any more by only increasing flows along the forward direction.In a traffic jam or in a situation of emergency evacuation,the network is often blocked by a saturated flow.Clearly,the smaller the value of the saturated flow is,the worse is the performance of the network.This gives rise to the minimum saturated flow problem in network analysis.In this paper we first show that the problem is NP-hard.Then,the relation between minimum saturated flows and maximum flows,as well as results in the algorithmic aspect,are presented.

关 键 词：网络分析 网络流 最小饱和流 紧急网络 饱和流 最大流 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]