New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs

Explore cutting-edge algorithms and complexity analysis for incremental single-source shortest paths (SSSP) in directed graphs in this 23-minute conference talk presented at an Association for Computing Machinery (ACM) event. Delve into the problem definition, examine the ES Tree and Lazy ES Tree data structures, and gain insights into new algorithmic approaches. Understand the challenges and hardness associated with solving SSSP problems in dynamic directed graphs, and discover how these findings contribute to the field of graph algorithms and theoretical computer science.