Report Number: CS-TR-80-794
Institution: Stanford University, Department of Computer Science
Title: Recent developments in the complexity of combinatorial algorithms
Author: Tarjan, Robert Endre
Date: June 1980
Abstract: The last three years have witnessed several major advances in the area of combinatorial algorithms. These include improved algorithms for matrix multiplication and maximum network flow, a polynomial-time algorithm for linear programming, and steps toward a polynomial-time algorithm for graph isomorphism. This paper surveys these results and suggests directions for future research. Included is a discussion of recent work by the author and his students on dynamic dictionaries, network flow problems, and related questions.