陕西师范大学学报（自然科学版）
陝西師範大學學報（自然科學版）
협서사범대학학보（자연과학판）
JOURNAL OF SHAANXI NORMAL UNIVERSITY(NATURAL SCIENCE EDITION)
2006年
1期
18-20
,共3页
网络流优化%最大共存流%ε优化流%流的拥挤度%边容量
網絡流優化%最大共存流%ε優化流%流的擁擠度%邊容量
망락류우화%최대공존류%ε우화류%류적옹제도%변용량
研究了网络中最大共存流的优化问题,提出了网络流优化的快速数值逼近算法.该算法用被定性的共存流的轮流选取取代了传统的共存流随机选取,用O(k(ε-2+lg k)lg n)(其中k是共存流数,n是节点数,ε是精度要求)个单个流的最小成本流的计算来定性计算最大共存流的逼近解.其优点是在不增加总的运算时间的前提下,显著地改进了已知的定性上界,并且可以达到目前已知的随机上界.
研究瞭網絡中最大共存流的優化問題,提齣瞭網絡流優化的快速數值逼近算法.該算法用被定性的共存流的輪流選取取代瞭傳統的共存流隨機選取,用O(k(ε-2+lg k)lg n)(其中k是共存流數,n是節點數,ε是精度要求)箇單箇流的最小成本流的計算來定性計算最大共存流的逼近解.其優點是在不增加總的運算時間的前提下,顯著地改進瞭已知的定性上界,併且可以達到目前已知的隨機上界.
연구료망락중최대공존류적우화문제,제출료망락류우화적쾌속수치핍근산법.해산법용피정성적공존류적륜류선취취대료전통적공존류수궤선취,용O(k(ε-2+lg k)lg n)(기중k시공존류수,n시절점수,ε시정도요구)개단개류적최소성본류적계산래정성계산최대공존류적핍근해.기우점시재불증가총적운산시간적전제하,현저지개진료이지적정성상계,병차가이체도목전이지적수궤상계.
