Extrait de l'introduction de "New Distance-Directed Algorithms for Maximum Flow and Parametric Maximum Flow Problems"
The maximum flow problem is one of the most fundamental network problems and has been investigated extensively in the literature (for example, by Ford and Fulkerson 1956, Dinic 1970, Edmonds and Karp 1972, Karzanov 1974, Cherkasky 1977, Malhotra et. al 1978, Galil 1980, Galil and Naamad 1980, Sleator and Tarjan 1983, Gabow 1985, Goldberg 1985, Goldberg and Tarjan 1986, Ahuja and Orlin 1987). Efficient algorithms for computing maximum flows are important not only because they are applied directly to the analysis of traffic or communication networks, but are often employed in the subproblems of other network problems. Some of the network problems whose algorithms use the maximum flow algorithm as a subroutine are the time-cost tradeoff problem in CPM networks (Fulkerson 1961, Kelley 1961), the parametric network feasibility problem (Minieka 1972), the network design problem (Hu 1974) and the minimax transportation problem (Ahuja 1986). Moreover, it plays an important role in solving the minimum cost flow problem (Rock 1980, Tardos 1985, Bland and Jensen 1985). Recently, Goldberg and Tarjan (1987) have developed the fastest known algorithm for the minimum cost flow problem using an extension of their maximum flow algorithm as a major subroutine.
Ford and Fulkerson (1956) formulated the maximum flow problem and solved it using their augmenting path algorithm. Edmonds and Karp (1972) showed that by augmenting flows along shortest paths, the augmenting path algorithm runs in time O(nm 2 ) on networks with n nodes and m arcs. Independently, Dinic (1970) suggested an O(n 2 m) algorithm which proceeds by constructing shortest path networks (known as layered networks) and establishing blocking (or maximal) flows in these networks. Dinic's algorithm has been studied extensively by researchers who dramatically improved its worst case running time using sophisticated data structures. Most notable among these improvements is the 'dynamic trees' algorithm Their algorithm runs in O(nm log n) developed by Sleator and Tarjan (1983). steps. Gabow's (1985) scaling algorithm also uses Dinic's algorithm as a major subroutine.
Recently, Goldberg (1985) and Goldberg and Tarjan (1986) developed a new approach to solve the maximum flow problem that does not construct layered networks but instead maintains "distance labels". Informally, a distance label of a node is an integral lower bound on the length of the shortest augmenting path from that node to the sink. A distance label is called exact if it equals the length of the shortest augmenting path, and approximate otherwise. Distance labels have several advantages over layered networks. They are simpler to understand, easier to manipulate and have led to more efficient algorithms. We refer to algorithms that utilize distance labels as distance-directed algorithms. Goldberg (1985) developed the first distance-directed algorithm. Subsequently, Goldberg and Tarjan (1986) developed improved distance-directed algorithms. Currently, the fastest algorithm to solve the maximum flow problem, due to Ahuja and Orlin (1987a), is also a distance-directed algorithm. Its running time is O(nm + n 2 log U) steps, where U is an upper bound on the capacities of arcs directed from the source. So far all the proposed distance-directed algorithms have been preflow based algorithms, similar in essence to Karzanov's (1974) algorithm.
