Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
From MaRDI portal
Publication:5002715
DOI10.4230/LIPIcs.ICALP.2018.42zbMath1499.68403OpenAlexW2885939955MaRDI QIDQ5002715
Publication date: 28 July 2021
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9046/pdf/LIPIcs-ICALP-2018-42.pdf/
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Data structures (68P05) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- Matrix multiplication via arithmetic progressions
- Approximating geometric bottleneck shortest paths
- Variations on the bottleneck paths problem
- Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Incremental algorithms for minimal length paths
- Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths