AN INCREMENTAL ALGORITHM FOR A GENERALIZATION OF THE SHORTEST-PATH PROBLEM

The grammar problem, a generalization of the single-source shortest-pa th problem introduced by D. E. Knuth (Inform. Process. Lett. 6(1) (197 7), 1-5) is to compute the minimum-cost derivation of a terminal strin g from each nonterminal of a given context-free grammar, with the cost of a derivation being suitably defined. This problem also subsumes th e 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 eff icient incremental algorithm for the single-source shortest-path probl em with positive edge lengths. The aspect of our work that distinguish es it from other work on the dynamic shortest-path problem is its abil ity to handle ''multiple heterogeneous modifications'': between update s, the input graph is allowed to be restructured by an arbitrary mixtu re of edge insertions, edge deletions, and edge-length changes. (C) 19 96 Academic Press, Inc.