Tight Hardness for Shortest Cycles and Paths in Sparse Graphs

Tight Hardness for Shortest Cycles and Paths in Sparse Graphs

Fine-grained reductions have established equivalences between many core problems with Õ(n3)-time algorithms on n-node weighted graphs, such as Shortest Cycle, All-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, and so on. These problems also have Õ(mn)-time algorithms...

Full description

Bibliographic Details
Main Authors: Lincoln, Andrea I, Williams, Virginia Vassilevska, Williams, Richard Ryan
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Book
Language:English
Published: Society for Industrial and Applied Mathematics 2020
Online Access:https://hdl.handle.net/1721.1/125617

Internet

https://hdl.handle.net/1721.1/125617

Similar Items