Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs.
From MaRDI portal
Publication:5002718
DOI10.4230/LIPIcs.ICALP.2018.43zbMath1499.68266arXiv1808.10658OpenAlexW2963924681MaRDI QIDQ5002718
Yuanhang Xie, Ran Duan, Kaifeng Lyu
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1808.10658
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Matrix multiplication via arithmetic progressions
- An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
- Time bounds for selection
- Mosaicking of Aerial Photographic Maps Via Seams Defined by Bottleneck Shortest Paths
- An optimal minimum spanning tree algorithm
- Maximal Flow Through a Network
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Algorithms for two bottleneck optimization problems
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Finding Minimum Spanning Trees
- A randomized linear-time algorithm to find minimum spanning trees
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Fibonacci heaps and their uses in improved network optimization algorithms
- Multiplying matrices faster than coppersmith-winograd
- Depth-First Search and Linear Graph Algorithms
