Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem

Abstract

Goldfarb and Hao have proposed a network simplex algorithm that will solve a maximum flow problem on an n-vertex, m-arc network in at most nm pivots and O(n squared m) time. In this paper we describe how to implement their algorithm to run in O(nmlog n) time by using an extension of the dynamic tree data structure of Sleator and Tarjan. This bound is less than a logarithmic factor larger than that of any other known algorithm for the problem. Keywords: Algorithms; Complexity; Data structures; Dynamic trees; Graphs; Linear programming; Maximum flow; Network flow; Network optimization.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1988
Accession Number
ADA214691

Entities

People

  • Andrew V. Goldberg
  • Michael D. Grigoriadis
  • Robert Tarjan

Organizations

  • Princeton University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Military Research
  • New Brunswick
  • Numbers
  • Real Numbers
  • Residuals
  • Rotation
  • Simplex Method
  • Simulations
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.