Use of dynamic trees in a network simplex algorithm for the maximum flow problem

DOI10.1007/BF01594940zbMath0743.90107MaRDI QIDQ1176566

Michael D. Grigoriadis, Andrew V. Goldberg, Robert Endre Tarjan

Publication date: 25 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

dynamic treesprimal network simplex algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Deterministic network models in operations research (90B10)

Related Items (17)

Equivalence of the primal and dual simplex algorithms for the maximum flow problem ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ On strongly polynomial dual simplex algorithms for the maximum flow problem ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Strongly polynomial dual simplex methods for the maximum flow problem ⋮ Unnamed Item ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem ⋮ Maximum flow problem in wireless ad hoc networks with directional antennas ⋮ Polynomial-time primal simplex algorithms for the minimum cost network flow problem ⋮ An exterior simplex type algorithm for the minimum cost network flow problem ⋮ A polynomial-time simplex method for the maximum \(k\)-flow problem ⋮ Polynomial dual network simplex algorithms ⋮ A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time ⋮ Computational investigations of maximum flow algorithms ⋮ On the maximum capacity augmentation algorithm for the maximum flow problem ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• A data structure for dynamic trees
• A Fast and Simple Algorithm for the Maximum Flow Problem
• An efficient implementation of the network simplex method
• Amortized Computational Complexity
• Self-adjusting binary search trees
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
• A network simplex method

This page was built for publication: Use of dynamic trees in a network simplex algorithm for the maximum flow problem