Incremental computation concerns the re-computation of output after a change in the input, whereas algorithms and programs usually derive their output directly from their input. This book investigates the concept of incremental computation and dynamic algorithms in general and provides a variety of new results, especially for computational problems from graph theory: the author presents e.g. efficient incremental algorithms for several shortest-path problems as well as incremental algorithms for the circuit value annotation problem and for various computations in reducible flow graphs.
Author(s): G. Ramalingam (eds.)
Series: Lecture Notes in Computer Science 1089
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1996
Language: English
Pages: 196
Tags: Algorithm Analysis and Problem Complexity; Combinatorics; Computation by Abstract Devices; Operating Systems
Introduction....Pages 1-6
On incremental algorithms and their complexity....Pages 7-24
Terminology and notation....Pages 25-29
Incremental algorithms for shortest-path problems....Pages 30-51
Generalizations of the shortest-path problem....Pages 52-77
An incremental algorithm for a generalization of the shortest-path problem....Pages 78-100
Incremental algorithms for the circuit value annotation problem....Pages 101-129
Inherently unbounded incremental computation problems....Pages 130-146
Incremental algorithms for reducible flowgraphs....Pages 147-168
Conclusions....Pages 169-171
