caa a22 4500 445804963 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9328-x doi (NATIONALLICENCE)springer-10.1007/s00453-009-9328-x All-Pairs Bottleneck Paths in Vertex Weighted Graphs [Elektronische Daten] [Asaf Shapira, Raphael Yuster, Uri Zwick] Let G=(V,E,w) be a directed graph, where w:V→ℝ is a weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex on the path. For two vertices u,v the capacity from u to v, denoted byc(u,v), is the maximum bottleneck weight of a path from u to v. In the All-Pairs Bottleneck Paths (APBP) problem the task is to find the capacities for all ordered pairs of vertices. Our main result is an O(n 2.575) time algorithm for APBP. The exponent is derived from the exponent of fast matrix multiplication. A variant of our algorithm computes shortest paths of maximum bottleneck weight. Let d(u,v) denote the (unweighted) distance from u to v, and let sc(u,v) denote the maximum bottleneck weight of a path from u to v having length d(u,v). The All-Pairs Bottleneck Shortest Paths (APBSP) problem is to compute sc(u,v) for all ordered pairs of vertices. We present an algorithm for APBSP whose running time is O(n 2.86). Springer Science+Business Media, LLC, 2009 Bottleneck paths nationallicence Shortest paths nationallicence Directed weighted graphs nationallicence Shapira Asaf School of Mathematics and College of Computing, Georgia Institute of Technology, 30332, Atlanta, GA, USA aut Yuster Raphael Department of Mathematics, University of Haifa, 31905, Haifa, Israel aut Zwick Uri School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut Algorithmica Springer-Verlag 59/4(2011-04-01), 621-633 0178-4617 59:4<621 2011 59 453 https://doi.org/10.1007/s00453-009-9328-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9328-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Shapira Asaf School of Mathematics and College of Computing, Georgia Institute of Technology, 30332, Atlanta, GA, USA aut NATIONALLICENCE 700 1- Yuster Raphael Department of Mathematics, University of Haifa, 31905, Haifa, Israel aut NATIONALLICENCE 700 1- Zwick Uri School of Computer Science, Tel Aviv University, 69978, Tel Aviv, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 621-633 0178-4617 59:4<621 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer