A deficit scaling algorithm for the minimum flow problem

被引：7
作者：
Ciupala, Laura [1 ]
机构：
[1] Transilvania Univ Brasov, Fac Math & Informat, Dept Comp Sci, Brasov, Romania
来源：
SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES | 2006年 / 31卷 / 3期
关键词：
network flow; network algorithms; minimum flow problem; scaling technique;
D O I：
10.1007/BF02703378
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
In this paper, we develop a new preflow algorithm for the minimum flow problem, called deficit scaling algorithm, This is a special implementation of the generic preflow algorithm for the minimum How problem developed by Ciurea and Ciupala earlier. The bottleneck operation in the generic preflow algorithm is the number of noncancelling pulls. Using the scaling technique (i.e. selecting the active nodes with sufficiently large deficits), we reduce the number of noncancelling pulls to O(n(2) log (c) over bar) and obtain an O(nm + n(2) log (c) over bar) algorithm.
引用
收藏
页码：227 / 233
页数：7
相关论文
共 50 条
  • [1] A deficit scaling algorithm for the minimum flow problem
    Laura Ciupală
    Sadhana, 2006, 31 : 227 - 233
  • [2] The wave preflow algorithm for the minimum flow problem
    Ciupala, Laura
    MACMESE 2008: PROCEEDINGS OF THE 10TH WSEAS INTERNATIONAL CONFERENCE ON MATHEMATICAL AND COMPUTATIONAL METHODS IN SCIENCE AND ENGINEERING, PTS I AND II, 2008, : 473 - +
  • [3] A parallel algorithm for the minimum flow problem in bipartite networks
    Ciupala, Laura
    Ciurea, Eleonor
    PROCEEDINGS OF THE 12TH WSEAS INTERNATIONAL CONFERENCE ON COMPUTERS , PTS 1-3: NEW ASPECTS OF COMPUTERS, 2008, : 203 - +
  • [4] A parallel FIFO preflow algorithm for the minimum flow problem
    Ciupala, Laura
    Ciurea, Eleonor
    INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, 2006, 1 : 135 - 139
  • [5] A highest-label preflow algorithm for the minimum flow problem
    Ciupala, Laura
    Ciurea, Eleonor
    PROCEEDING OF THE 11TH WSEAS INTERNATIONAL CONFERENCE ON COMPUTERS: COMPUTER SCIENCE AND TECHNOLOGY, VOL 4, 2007, : 167 - +
  • [6] A scaling out-of-kilter algorithm for minimum cost flow
    Ciupala, L
    CONTROL AND CYBERNETICS, 2005, 34 (04): : 1169 - 1174
  • [7] A faster capacity scaling algorithm for minimum cost submodular flow
    Fleischer, L
    Iwata, S
    McCormick, ST
    MATHEMATICAL PROGRAMMING, 2002, 92 (01) : 119 - 139
  • [8] A strongly polynomial algorithm for the minimum maximum flow degree problem
    Campelo, Manoel
    Matias, Jhonata
    OPERATIONS RESEARCH LETTERS, 2023, 51 (01) : 67 - 71
  • [9] A deterministic annealing algorithm for the minimum concave cost network flow problem
    Dang, Chuangyin
    Sun, Yabin
    Wang, Yuping
    Yang, Yang
    NEURAL NETWORKS, 2011, 24 (07) : 699 - 708
  • [10] Shortest conditional decreasing path algorithm for the parametric minimum flow problem
    Ciurea, Eleonor
    Parpalea, Mircea
    BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE, 2013, 56 (04): : 387 - 401
12345