Author:

Keywords:

approximation algorithm, arc reach, network hierarchies, shortest paths

Abstract:

© Copyright 2014 ACM. The reach of an arc in a network can intuitively be described as an indication of the maximum length of the shortest paths of the digraph that pass through this arc. This concept captures the natural hierarchy of any type of network, in an accurate and comprehensive manner. Traditional reach approximation algorithms compute upper bounds to these reaches and require computation of a partial shortest path tree rooted in all vertices of the network. Tailored for route computation enhancement, these methods yield exact reaches in the low reach spectrum, whereas higher reaches are kept set to infinity. The present paper introduces an iterative method for gener-ating lower bounds to the reaches of the arcs in a network. This method is suitable for situations where it is more impor-tant to know the order of magnitude of the high than these of the low reaches and where very low or variable calcula-tion times are required. An experiment in an attractiveness-weighted cycling network of considerable size shows that the iterative method steadily approximates the arc reaches for a low number of iterations. The approximation algorithm has been formulated for arc reaches in a digraph but can easily be adapted to a vertex reach version and works in undirected graphs as well.