-
Article
Use of dynamic trees in a network simplex algorithm for the maximum flow problem
Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n 2 m) time. In this paper ...
-
Article
Finding minimum-cost flows by double scaling
Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(l...
-
Article
An efficient cost scaling algorithm for the assignment problem
The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the me...
-
Article
Shortest paths algorithms: Theory and experimental evaluation
We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theor...
-
Article
Negative-cycle detection algorithms
-
Article
Maximum skew-symmetric flows and matchings
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate flows in antisymmetrical digra...
-
Article
An exact combinatorial algorithm for minimum graph bisection
We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is b...