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

ISSN： 0196-6774

Source： Journal of Algorithms, Vol.21, Iss.2, 1996-09, pp. : 267-305

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The grammar 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.