𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by G. Ramalingam; Thomas Reps

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
363 KB
Volume
21
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

The grammar problem, a generalization of the single-source shortest-path prob-Ž Ž . Ž . . lem 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.

πŸ“œ SIMILAR VOLUMES

Dual algorithms for the shortest path tr
Dual algorithms for the shortest path tree problem
✍ Pallottino, Stefano; ScutellοΏ½, Maria Grazia πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 117 KB πŸ‘ 2 views

We consider dual approaches for the Shortest Path Tree problem. After a brief introduction to the problem, we review the most important dual algorithms which have been described in the literature for its solution and propose a new family of dual ascent algorithms. In these algorithms, ''local'' and

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
✍ Mirchandani, Prakash πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 288 KB πŸ‘ 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a

An efficient implementation of an algori
An efficient implementation of an algorithm for findingK shortest simple paths
✍ Hadjiconstantinou, E.; Christofides, N. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 263 KB πŸ‘ 1 views

In this article, we present an efficient computational implementation of an algorithm for finding the K shortest simple paths connecting a pair of vertices in an undirected graph with n vertices, m arcs, and nonnegative arc lengths. A minimal number of intermediate paths is formed based on the metho

A Simple Parallel Algorithm for the Sing
A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs
✍ Jesper L. TrΓ€ff; Christos D. Zaroliagis πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 216 KB

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n 2= +n 1&= ) log n) time, performing O(n 1+= log n) work for any 0<=<1Γ‚2. The strength of

New dynamic programming algorithms for t
New dynamic programming algorithms for the resource constrained elementary shortest path problem
✍ Giovanni Righini; Matteo Salani πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 173 KB

## Abstract The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch‐and‐price algorithms for vehicle‐routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare three methods. The first method