Campus Event Calendar
Event Entry
What and Who
Bellman-Ford is optimal for shortest hop-bounded paths
Adam Polak
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 8 December 2022
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
The talk will be about the problem of finding shortest paths 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. We show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. This 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.
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
5272788807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
It will be a board-talk. If you wish to attend the talk online but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.
Roohani Sharma, 12/06/2022 14:56
Roohani Sharma, 12/05/2022 14:31 -- Created document.
Roohani Sharma, 12/05/2022 14:31 -- Created document.