Some Extensions of the Bottleneck Paths Problem

Autor:	Tong-Wook Shinn, Tadao Takaoka
Rok vydání:	2014
Předmět:	Combinatorics Problem domain Combinatorial algorithms Omega Bottleneck Graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Algorithms and Computation ISBN: 9783319046563 WALCOM
DOI:	10.1007/978-3-319-04657-0_18
Popis:	We extend the well known bottleneck paths problem in two directions for directed unweighted graphs with positive real edge capacities. Firstly we narrow the problem domain and compute the bottleneck of the entire network in O(mlogn) time, where m and n are the number of edges and vertices in the graph, respectively. Secondly we enlarge the domain and compute the shortest paths for all possible bottleneck 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(\sqrt{t}n^{(\omega+9)/4})\) time, where t is the number of distinct edge capacities and O(n ω ) is the time taken to multiply two n-by-n matrices over a ring. We also discuss practical applications for these new problems.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::fe53a4dc68e071911a545b56cd1e386d https://doi.org/10.1007/978-3-319-04657-0_18 Zobrazit plný text záznamu