运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2014年
4期
96-104
,共9页
网络流%最小覆盖流%多项式时间算法
網絡流%最小覆蓋流%多項式時間算法
망락류%최소복개류%다항식시간산법
network flow%minimum cover flow%polynomial-time algorithm
网络流理论中最基本的模型是最大流及最小费用流问题.为研究堵塞现象,文献中出现了最小饱和流问题,但它是NP-难的.研究类似的最小覆盖流问题,即求一流,使每一条弧的流量达到一定的额定量,而流的值为最小.主要结果是给出多项式时间算法,并应用于最小饱和流问题.
網絡流理論中最基本的模型是最大流及最小費用流問題.為研究堵塞現象,文獻中齣現瞭最小飽和流問題,但它是NP-難的.研究類似的最小覆蓋流問題,即求一流,使每一條弧的流量達到一定的額定量,而流的值為最小.主要結果是給齣多項式時間算法,併應用于最小飽和流問題.
망락류이론중최기본적모형시최대류급최소비용류문제.위연구도새현상,문헌중출현료최소포화류문제,단타시NP-난적.연구유사적최소복개류문제,즉구일류,사매일조호적류량체도일정적액정량,이류적치위최소.주요결과시급출다항식시간산법,병응용우최소포화류문제.
