登入選單

返回Google圖書搜尋

Finding Minimum-cost Circulations by Canceling Negative Cycles

Andrew V. GoldbergMASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE.R. E. Tarjan

出版	Laboratory for Computer Science, Massachusetts Inst. of Technology, 1987
URL	http://books.google.com.hk/books?id=AaCvNwAACAAJ&hl=&source=gbs_api

註釋

A classical algorithm for finding a minimum cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in 0(nm(log n)min(log(nC), mlogn)) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C. This bound is comparable to those of the fastest previously known algorithms. Keywords: Network flows, Minimum cost flow, Combinatorial optimization.