Skip to main content

9 Result(s)

within Andrew V. Goldberg Remove this filter Mathematics Remove this filter

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

    Chapter and Conference Paper

    Negative-cycle detection algorithms

    We study the problem of finding a negative length cycle in a network. An algorithm for the negative cycle problem combines a shortest path algorithm and a cycle detection strategy. We study various combination...

    Boris V. Cherkassky, Andrew V. Goldberg in Algorithms — ESA '96 (1996)

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

  6. No Access

    Article

    Path problems in skew-symmetric graphs

    We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for ...

    Andrew V. Goldberg, Alexander V. Karzanov in Combinatorica (1996)

  7. No Access

    Article

    Negative-cycle detection algorithms

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

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

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