-
题名最小饱和流问题的多项式时间可解变形(英文)
- 1
-
-
作者
林浩
林澜
-
机构
河南工业大学理学院
同济大学电子与信息工程学院
-
出处
《工程数学学报》
CSCD
北大核心
2014年第3期406-416,共11页
-
基金
The National Natural Science Foundation of China(11101383
61373106)
the Natural Science Foundation of Henan Province(2010B110006)
-
文摘
最小饱和流问题就是求具有最小值的饱和流.此问题起源于紧急疏散和交通阻塞的研究,并且已知是一个NP-困难问题.本文探讨两个特殊情形:一个限定问题是寻求给定截集的最小饱和流,一个松弛问题是寻求最小双向容量截集.对于前者,通过构造一个辅助网络AN(S)及运用最大流算法,建立一个多项式时间算法,并证明其复杂性是O(n3).对于后者,通过构造一个单向网络N′,将问题转化为一个最小容量截问题.但是这个新网络N′可能包含负容量的弧,一般不易求解.当单向网络N′是平面网络时,我们建立了多项式时间算法.
-
关键词
网络最优化
网络饱和流
最小饱和流问题
多项式时间可解情形
-
Keywords
network optimization
saturated flows
the minimum saturated flow problem
polynomial-time algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
-