Report Number: CS-TR-77-609
Institution: Stanford University, Department of Computer Science
Title: Complexity of combinatorial algorithms
Author: Tarjan, Robert Endre
Date: April 1977
Abstract: This paper examines recent work on the complexity of
combinatorial algorithms, highlighting the aims of the work,
the mathematical tools used, and the important results.
Included are sections discussing ways to measure the
complexity of an algorithm, methods for proving that certain
problems are very hard to solve, tools useful in the design
of good algorithms, and recent improvements in algorithms for
solving ten representative problems. The final section
suggests some directions for future research.