Recent Developments in the Complexity of Combinatorial Algorithms
Robert Endre Tarjan · Defense Technical Information Center (DTIC) · 1980
Several major advances in the area of combinatorial algorithms 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.