An algorithm for finding the absolute center of a network (Q1173797)

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\cdot n\cdot\log n)\) for unweighted networks and \(O(k\cdot m\cdot n\cdot\log n)\) 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 \textit{E. Minieka} [Networks 11, No. 4, 351-355 (1981; Zbl 0738.90047)] for unweighted networks, and with the algorithm of \textit{O. Kariv} and \textit{S. L. Hakimi} [SIAM J. Appl. Math. 37, 513-538 (1979; Zbl 0432.90074)] for weighted networks. In both cases it gave good experimental results in terms of computer time.