Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs.

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

zbMATH Keywords

combinatorial optimizationgraph algorithmbottleneck path

Mathematics Subject Classification ID

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