Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators

Explore parallel approximate undirected shortest paths algorithms in this theory seminar presented by Peilin Zhong from Columbia University. Delve into the concept of low hop emulators and their application in solving graph problems efficiently. Learn about the Bellman-Ford algorithm, hopset construction, and the "Law of Amateur" in graph theory. Discover applications in submillimetre and strong submillimetre problems, and understand the highway example used to illustrate key concepts. Analyze the construction and performance of these algorithms, and consider open problems in the field. This comprehensive lecture, recorded on February 25, 2020, includes closed captions and is part of the Paul G. Allen School's theory seminar series.