Skip to main content

and
  1. No Access

    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 ...

    Andrew V. Goldberg, Michael D. Grigoriadis, Robert E. Tarjan in Mathematical Programming (1991)

  2. No Access

    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...

    Ravindra K. Ahuja, Andrew V. Goldberg, James B. Orlin in Mathematical Programming (1992)

  3. No Access

    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...

    Andrew V. Goldberg, Robert Kennedy in Mathematical Programming (1995)

  4. No Access

    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...

    Boris V. Cherkassky, Andrew V. Goldberg, Tomasz Radzik in Mathematical Programming (1996)

  5. No Access

    Article

    Negative-cycle detection algorithms

    Boris V. Cherkassky, Andrew V. Goldberg in Mathematical Programming (1999)

  6. No Access

    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...

    Andrew V. Goldberg, Alexander V. Karzanov in Mathematical Programming (2004)

  7. No Access

    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...

    Daniel Delling, Daniel Fleischman, Andrew V. Goldberg in Mathematical Programming (2015)