Consider a path between two vertices s and t in an undirected weighted graph G.

Question

Consider a path between two vertices s and t in an undirected weighted graph G. The bottleneck length of this path is the maximum weight of any edge in the path. The bottleneck distance between s and t is the minimum bottleneck length of any path from s to t. (If there are no paths from s to t, the bottleneck distance between s and t is .) Describe and analyze an algorithm to compute the bottleneck distance between every pair of vertices in an arbitrary undirected weighted graph. Assume that no two edges have the same weight.

Explanation / Answer

Let T = ( N, E') be the minimum cost spanning tree of graph G = ( N, E, w ). Let {i, j} be the maximum weight edge (bottleneck edge) of T . Fix node i and consider all nodes k in N { i } such that the unique path from i to k in T includes edge {i, j} . Call this set of nodes S . Note that i != S and j -> S . So, S and N S are non-empty sets. Hence, we can identify a cut ( S, N S ) such that {i, j} is the unique edge in E ' which crosses this cut. Let { k, l } be the edge which crosses this cut and belongs to minimum weight bottleneck.

Since T is the minimum cost tree of G we have w ({i, j}) = w ({k, l}). If {u, v} is the bottleneck edge
of the minimum weight bottleneck span ning tree then w ({i, j}) = w ({k, l}) = w ({u, v}). Hence, T must also be a minimum weight bottleneck tree.

Let G = (V, E, w) be a directed graph, where w : V -> R is an arbitrary 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 bottleneck weight, or the capacity, from u to v, denoted c(u, v), is the maximum bottleneck weight of a path from u to v. In the All-Pairs Bottleneck Paths (APBP). we have to find the bottleneck weights for all ordered pairs of vertices. Our main result is an O(n2.575) time algorithm. The exponent is derived from the exponent of fast matrix multiplication. Unlike the sub-cubic algorithm for the all-pairs shortest paths (APSP) problem, that only applies to bounded integer edge or vertex weights, the algorithm presented for APBP problem works for arbitrary large vertex weights.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.