Skip to main content
Springer Nature Link
Log in

Bounded Incremental Computation

  • Book
  • © 1996

Overview

Editors:
  1. G. Ramalingam
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1089)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book EUR 15.99 EUR 53.49
Discount applied Price includes VAT (Bulgaria)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

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.

Keywords

Table of contents (10 chapters)

  1. Front Matter

    Download chapter PDF

  2. Introduction

    Pages 1-6

  3. On incremental algorithms and their complexity

    Pages 7-24

  4. Terminology and notation

    Pages 25-29

  5. Incremental algorithms for shortest-path problems

    Pages 30-51

  6. Generalizations of the shortest-path problem

    Pages 52-77

  7. An incremental algorithm for a generalization of the shortest-path problem

    Pages 78-100

  8. Incremental algorithms for the circuit value annotation problem

    Pages 101-129

  9. Inherently unbounded incremental computation problems

    Pages 130-146

  10. Incremental algorithms for reducible flowgraphs

    Pages 147-168

  11. Conclusions

    Pages 169-171

  12. Back Matter

    Download chapter PDF
Back to top

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation