An algorithm for finding the absolute center of a network

DOI10.1016/0377-2217(90)90421-7MaRDI QIDQ1173797zbMATH OpenOpenAlexFDO

Authors Antonio Sforza

Publication date 25 June 1992

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(90)90421-7

zbMATH Keywords

absolute center of a networkunweighted networksweighted networks

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Review text

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.

Recommendations

• The absolute center of a network
• A polynomial time algorithm for finding the absolute center of a network
• The continuous center set of a network
• Some new algorithms for location problems on networks
• The absolute centre of a graph

Cites work

• A polynomial time algorithm for finding the absolute center of a network
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• scientific article; zbMATH DE number 3847184 (Why is no real title available?)
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph

Cited in

(14)

• Group centre and group median of a network
• Some new algorithms for location problems on networks
• Location and layout planning. A survey
• A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs
• scientific article; zbMATH DE number 4179135 (Why is no real title available?)
• scientific article; zbMATH DE number 4095237 (Why is no real title available?)
• A polynomial time algorithm for finding the absolute center of a network
• Biobjective center – balance graph location model^*
• The absolute center of a network
• scientific article; zbMATH DE number 1786155 (Why is no real title available?)
• Using weighted graphs features for fast searching their parameters
• Discrete center problems
• The continuous center set of a network
• The absolute centre of a graph

This page was built for publication: An algorithm for finding the absolute center of a network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1173797)