All Pairs Maximum Path Algorithms for an Average Path Value

Abstract

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, $ap{v}_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}.