Some extensions of the bottleneck paths problem

DOI10.1007/978-3-319-04657-0_18MaRDI QIDQ5746256zbMATH OpenOpenAlexFDO

Authors Tong-Wook Shinn, Tadao Takaoka

Publication date 18 February 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5815

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We extend the well known bottleneck paths problem in two directions for directed unweighted (unit edge cost) graphs with positive real edge capacities. Firstly we narrow the problem domain and compute the bottleneck of the entire network in $O(n^{omega}logn)$ time, where $O(n^{omega})$ is the time taken to multiply two $n$-by-$n$ matrices over ring. Secondly we enlarge the domain and compute the shortest paths for all possible flow amounts. We present a combinatorial algorithm to solve the Single Source Shortest Paths for All Flows (SSSP-AF) problem in $O(mn)$ worst case time, followed by an algorithm to solve the All Pairs Shortest Paths for All Flows (APSP-AF) problem in $O(sqrtd{n}^{(omega+9)/4})$ time, where $d$ is the number of distinct edge capacities. We also discuss real life applications for these new problems.

Recommendations

• Variations on the bottleneck paths problem
• Combining all pairs shortest paths and all pairs bottleneck paths problems
• All-pairs bottleneck paths in vertex weighted graphs
• All-pairs bottleneck paths in vertex weighted graphs
• Single-source bottleneck path algorithm faster than sorting for sparse graphs

Cited in

(9)

• Bottleneck shortest paths on a partially ordered scale
• Variations on the bottleneck paths problem
• Algebraic theory on shortest paths for all flows
• All-pairs bottleneck paths in vertex weighted graphs
• Single-source bottleneck path algorithm faster than sorting for sparse graphs
• scientific article; zbMATH DE number 7121921 (Why is no real title available?)
• Combining all pairs shortest paths and all pairs bottleneck paths problems
• Algebraic theory on shortest paths for all flows
• On efficient algorithms for bottleneck path problems with many sources

This page was built for publication: Some extensions of the bottleneck paths problem

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