Aspects of incremental computing
Safwan A. Bengelloun · 1982
The goal of research in the area of incremental computing is to develop fast algorithms for solving a succession of closely related problems. The pervasiveness of such sequences force the conclusion that incremental problems are fundamental to computer science. Indeed, by examining some of the common problem solving paradigms, we may be either led to general methods for solving incremental problems or to a set of open problems to be solved by specific means. This dissertation contains original results in four areas of incremental computing. We describe and implement a general incremental evaluator for an applicative language. We show how the technique of balancing can be used to solve a class of incremental problems. We consider depth-first search and develop incremental additive algorithms for graph 2-connectivity and 3-connectivity. Finally, we describe a new incremental primal sieve algorithm that is arithmetically as fast as the fastest known static algorithm.