The tree longest detour problem in a biconnected graph ?
In a biconnected graph, a detour is the best alternative path from a detour-starting vertex to the destination vertex. A detour-starting vertex is the vertex from which the original shortest path is changed. The longest detour (LD) problem is to find a detour-critical edge in a shortest path such that the removal of the edge results in the maximum distance increment. In this paper, we deal with the LD problem with respect to a shortest path tree. An efficient algorithm which takes O(m?(m,n)) time for finding a detour-critical edge in a shortest path tree is proposed, where ? is a functional inverse of Ackermanns function.
tree longest detour problem biconnected graphs detour-critical edge shortest path tree graph theory