Subcubic Min-Plus Product of Structured Matrices
The All-Pairs Shortest Paths (APSP) problem is one of the most basic problems in computer science. The fastest known algorithms for APSP in 𝑛-node graphs run in 𝑛³⁻⁰⁽¹⁾ time, and it is a big open problem whether a truly subcubic, 𝑂(𝑛³⁻ superscript 𝜀) for 𝜀 > 0 time algorithm exists for APSP. The...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139234 |