Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-127 | 6th December 2015 20:26

On the Optimality of Bellman--Ford Shortest Path Algorithm

RSS-Feed




Revision #1
Authors: Stasys Jukna, Georg Schnitger
Accepted on: 6th December 2015 20:26
Downloads: 2553
Keywords: 


Abstract:

We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum operations are allowed.



Changes to previous version:

Notions and proofs simplified. Section 6 added.


Paper:

TR15-127 | 7th August 2015 20:56

On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm





TR15-127
Authors: Stasys Jukna, Georg Schnitger
Publication: 7th August 2015 20:57
Downloads: 2846
Keywords: 


Abstract:

We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum operations are allowed.



ISSN 1433-8092 | Imprint