Elsevier

Journal of Algorithms

Volume 21, Issue 2, September 1996, Pages 267-305
Journal of Algorithms

Regular Article
An Incremental Algorithm for a Generalization of the Shortest-Path Problem

https://doi.org/10.1006/jagm.1996.0046Get rights and content

Abstract

Thegrammar problem, a generalization of the single-source shortest-path problem introduced by D. E. Knuth (Inform. Process. Lett.6(1) (1977), 1–5) is to compute the minimum-cost derivation of a terminal string from each nonterminal of a given context-free grammar, with the cost of a derivation being suitably defined. This problem also subsumes the problem of finding optimal hyperpaths in directed hypergraphs (under varying optimization criteria) that has received attention recently. In this paper we present an incremental algorithm for a version of the grammar problem. As a special case of this algorithm we obtain an efficient incremental algorithm for the single-source shortest-path problem with positive edge lengths. The aspect of our work that distinguishes it from other work on the dynamic shortest-path problem is its ability to handle “multiple heterogeneous modifications”: between updates, the input graph is allowed to be restructured by an arbitrary mixture of edge insertions, edge deletions, and edge-length changes.

References (0)

Cited by (0)

This work was supported in part by a David and Lucile Packard Fellowship for Science and Engineering, by the National Science Foundation under Grants DCR-8552602 and CCR-9100424, by the Defense Advanced Research Projects Agency, monitored by the Office of Naval Research under Contract N00014-88-K-0590, and by a grant from the Digital Equipment Corporation.

IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598. E-mail: [email protected]. This work was done when this author was at the University of Wisconsin.

E-mail: [email protected].

View full text