A fast algorithm for the minimax flow problem with 0/1 weights

被引：4
作者：
Han, CC
机构：
[1] Real-Time Computing Laboratory, Dept. of Elec. Eng. and Comp. Sci., University of Michigan, Ann Arbor
来源：
APPLIED MATHEMATICS LETTERS | 1997年 / 10卷 / 01期
关键词：
design and analysis of algorithms; f-saturated critical arcs; maximum flow; minimax flow; residual network;
D O I：
10.1016/S0893-9659(96)00103-6
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we define the minimax flow problem and design an O(k . M(n, m)) time optimal algorithm for a special case of the problem in which the weights on arcs are either O or 1, where n is the number of vertices, m is the number of arcs, k (where 1 less than or equal to k less than or equal to m) is the number of arcs with nonzero weights, and M(n; m) is the best time bound for finding a maximum flow in a network.
引用
收藏
页码：11 / 16
页数：6
相关论文
共 5 条
  • [1] IMPROVED ALGORITHMS FOR BIPARTITE NETWORK FLOW
    AHUJA, RK
    ORLIN, JB
    STEIN, C
    TARJAN, RE
    [J]. SIAM JOURNAL ON COMPUTING, 1994, 23 (05) : 906 - 933
  • [2] A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PROBLEM
    AHUJA, RK
    ORLIN, JB
    [J]. OPERATIONS RESEARCH, 1989, 37 (05) : 748 - 759
  • [3] BONDY JA, 1976, GRAPH THEORY APPLICA
  • [4] Ford L. R., 1956, Canadian journal of Mathematics, V8, P399, DOI [DOI 10.4153/CJM-1956-045-5, 10.4153/CJM-1956-045-5]
  • [5] Tarjan R, 1983, DATA STRUCTURES NETW
1