An algorithm for finding the absolute center of a network

An algorithm for finding the absolute center of a network

0.00 Avg rating0 Votes
Article ID: iaor19921163
Country: Netherlands
Volume: 48
Issue: 3
Start Page Number: 376
End Page Number: 390
Publication Date: Oct 1990
Journal: European Journal of Operational Research
Authors:
Abstract:

An algorithm for finding the absolute center of a network is proposed. Point-vertex distance functions are not explicitly used, but only the knowledge of the shortest distance matrix between all pairs of vertices is required. The value of the network radius is initially assumed as an upper bound of the absolute radius. Each edge is examined to find a local absolute center better than or equivalent to the current one. In this way the algorithm finds the absolute center or all the equivalent absolute centers. The required computational effort is O(mënëlogn) for unweighted networks and O(këmënëlogn) for weighted networks, where m is the number of edges, n the number of vertices and k a factor depending on the required precision and vertex weight distribution. The algorithm was applied to a sample of small and medium size randomly generated networks and compared with the algorithm of Minieka for unweighted networks, and with the algorithm of Kariv and Hakimi for weighted networks. In both cases it gave good experimental results in terms of computer time.

Reviews

Required fields are marked *. Your email address will not be published.