All‐Pairs Bottleneck Paths in Vertex Weighted Graphs

All‐Pairs Bottleneck Paths in Vertex Weighted Graphs

0.00 Avg rating0 Votes
Article ID: iaor20112416
Volume: 59
Issue: 4
Start Page Number: 621
End Page Number: 633
Publication Date: Apr 2011
Journal: Algorithmica
Authors: , ,
Keywords: networks: path
Abstract:

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 by c(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.

Reviews

Required fields are marked *. Your email address will not be published.