New algorithms and hardness for incremental single-source shortest paths in directed graphs

DOI10.1145/3357713.3384236OpenAlexW3035518111MaRDI QIDQ5144905

Nicole Wein, Maximilian Probst Gutenberg, Virginia Vassilevska Williams

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.10751

zbMATH Keywords

shortest pathdynamic algorithmsingle source shortest pathconditional lower bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Range updates and range sum queries on multidimensional points with monoid weights ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time

This page was built for publication: New algorithms and hardness for incremental single-source shortest paths in directed graphs