An Incremental Algorithm for a Generalization of the
Shortest-Path Problem
G. Ramalingam and Thomas Reps
The grammar problem, a generalization of the single-source
shortest-path problem introduced by Knuth, is to compute the
minimum-cost derivation of a terminal string from each non-terminal 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.
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin