登入選單

返回Google圖書搜尋

Tight Bounds on the Number of Minimum-mean Cycle Cancellations

Tomasz Radzik

出版	Department of Computer Science, Stanford University, 1990
URL	http://books.google.com.hk/books?id=lcaRuwEACAAJ&hl=&source=gbs_api

註釋

Abstract: "We prove a tight [theta](min(nm log(nC), nm4)) bound on the number of iterations of the minimum-mean cycle canceling algorithm of Goldberg and Tarjan [12]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations to O(nm4). We also give an improved version of the maximum-mean cut canceling algorithm of [6], which is a dual of the minimum-mean cycle canceling algorithm. Our version of the dual algorithm runs in O(nm4) iterations."