Page 1

Displaying 1 – 10 of 10

Showing per page

Labeled shortest paths in digraphs with negative and positive edge weights

Phillip G. Bradford, David A. Thomas (2009)

RAIRO - Theoretical Informatics and Applications

This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett et al. [SIAM J. Comput.30 (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based closely...

Currently displaying 1 – 10 of 10

Page 1