Accession Number:

ADA214691

Title:

Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem

Descriptive Note:

Corporate Author:

PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

Report Date:

1988-10-01

Pagination or Media Count:

19.0

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 On squared m time. In this paper we describe how to implement their algorithm to run in Onmlog 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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE