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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/80/794/CS-TR-80-794.pdf