One effective algorithm for finding a minimum cut of any transport network
[摘要] Finding the minimal cut on the directed graph is an important task that has not yet been solved in a general form. The solution of this problem allows one to find "the pipeline bottleneck" of the transport network and manage changing flows efficiently. In this article, authors discussed a new algorithm for solving this problem, built on the basis of consideration of the corresponding dual problem.
[发布日期] [发布机构] National Research Nuclear University, MEPhI (Moscow Engineering Physics Institute), 31 Kashirskoe shosse, Moscow; 115409, Russia^1;Gazprom VNIIGAZ LLC, box 130, Moscow; 115583, Russia^2
[效力级别] 数学 [学科分类]
[关键词] Algorithm for solving;Dual problem;Effective algorithms;Minimum cut;Transport networks [时效性]
