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

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

Research output: Contribution to journalArticle

38 Scopus citations

Abstract

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on an n-vertex, m-arc network in at most nm pivots and O(n2m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm log n). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.

Original languageEnglish (US)
Pages (from-to)277-290
Number of pages14
JournalMathematical Programming
Volume50
Issue number1-3
DOIs
StatePublished - Mar 1 1991

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Algorithms
  • complexity
  • data structures
  • dynamic trees
  • graphs
  • linear programming
  • maximum flow
  • network flow
  • network optimization

Fingerprint Dive into the research topics of 'Use of dynamic trees in a network simplex algorithm for the maximum flow problem'. Together they form a unique fingerprint.

  • Cite this