Eventi del

18 2023 12:00 - 13:00
Room 3-E4-SR03

Bellman–Ford is optimal (for shortest hop-bounded paths)

Scarica il programma

ADAM POLAK - Università Bocconi

Abstract: This talk will be about the problem of finding a shortest s-t path using at most h edges in edge-weighted graphs. The Bellman–Ford algorithm solves this problem in O(hm) time, where m is the number of edges. I will show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. This lower bound can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman-Ford algorithm. This is joint work with Tomasz Kociumaka (MPI Informatics).

 

For further information please contact: arianna.aliberti@unibocconi.it