Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

DOI10.4230/LIPIcs.ICALP.2018.42zbMath1499.68403OpenAlexW2885939955MaRDI QIDQ5002715

Ran Duan, Hanlin Ren

Publication date: 28 July 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9046/pdf/LIPIcs-ICALP-2018-42.pdf/

zbMATH Keywords

combinatorial optimizationgraph theoryapproximation algorithms

Mathematics Subject Classification ID

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