A polynomial time algorithm for finding the absolute center of a network. (English) Zbl 0738.90045

Summary: The absolute center of a network is any vertex or point on an edge such that the distance from it to the vertex farthest from it is as small as possible. We present a polynomial time algorithm for finding an absolute center. This algorithm is combinatorial in nature and requires only knowledge of the shortest path distances between all pairs of vertices.


90B80 Discrete location and assignment
90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI


[1] Graph Theory, An Algorithmic Approach, Academic, New York, 1975. · Zbl 0321.94011
[2] Hakimi, Oper. Res. Soc. Am. 12 pp 450– (1964)
[3] and , Locations on Networks, MIT Press, Cambridge, MA, 1979.
[4] Optimization Algorithms for Networks and Graphs, Marcel Dekker, New York, 1978.
[5] Graphs and Networks, An Introduction, Auerbach, Princeton, NJ, 1971.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.