In search of the fastest algorithm

Problems from many disciplines are frequently reduced to graph theoretic questions. This leaves the challenge of finding a solution to the graph problem as efficiently (cheaply) as possible. We will discuss techniques by which some of these questions may be answered in what is more or less a single scan of the input. Our attention then turns to problems that seem a little harder; that is, to problems for which there are trivially algorithms taking time polynomial in the amount of input, but no known algorithms which take time linear in the amount of data. This class includes, among many other problems, maximum matching in bipartite graphs and digraph transitive closure. We will discuss surprisingly fast algorithms for certain of these problems and lament our inability either to do better or to prove we cannot do better.