On efficient algorithms for bottleneck path problems with many sources

DOI10.1007/S11590-024-02113-0MaRDI QIDQ6542462zbMATH OpenFDO

Authors Kirill V. Kaymakov, D. S. Malyshev

Publication date 22 May 2024

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S11590-024-02113-0

zbMATH Keywords

bottleneck path problemcomputational complexitydesign and analysis of algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Some extensions of the bottleneck paths problem
• Variations on the bottleneck paths problem
• Single-source bottleneck path algorithm faster than sorting for sparse graphs
• Bottleneck flows in unit capacity networks
• All-pairs bottleneck paths in vertex weighted graphs

Cites work

• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• An improved equivalence algorithm
• Fast algorithms for (, )-matrix multiplication and bottleneck shortest paths
• Fast Algorithms for Finding Nearest Common Ancestors
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 5485494 (Why is no real title available?)
• scientific article; zbMATH DE number 3478389 (Why is no real title available?)
• scientific article; zbMATH DE number 1947385 (Why is no real title available?)
• scientific article; zbMATH DE number 6829368 (Why is no real title available?)
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Recursive Star-Tree Parallel Data Structure
• Set Merging Algorithms
• Single-source bottleneck path algorithm faster than sorting for sparse graphs
• The level ancestor problem simplified
• The Min-Max Spanning Tree Problem and some extensions
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Variations on the bottleneck paths problem
• Worst-case Analysis of Set Union Algorithms
• Über ein Minimalproblem.

Cited in

(2)

• Efficient computation of all tolerances in the sparse maxmin path problem
• Efficient online sensitivity analysis for the injective bottleneck path problem

This page was built for publication: On efficient algorithms for bottleneck path problems with many sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6542462)