All Pairs Maximum Path Algorithms for an Average Path Value

Let \( G(V, E) \) be a weighted connected simple graph. Given a pair of vertices \( u, v \in V \), let \( Max(u, v) \) denote the maximum average path value over all simple paths from \( u \) to \( v \). For a given simple path from \( u \) to \( v \), the average path value, \( apv_P(u, v) = \frac{min(P)}{length(P)} \), where \( min(P) \) is the weight of the minimum weight edge in the path \( P \) and \( length(P) \) is the number of edges in \( P \). This notion of average path value has been used in the analysis of social networks. Algorithms are presented for the calculation of \emph{average path value}.