The absolute centre of a graph

DOI10.1016/0166-218X(84)90004-0MaRDI QIDQ793644zbMATH OpenFDO

Authors R. A. Cuninghame-Green

Publication date 1984

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(84)90004-0

zbMATH Keywords

absolute centre of a graphcomputational complexityfacility locationglobal minimisationpiecewise-linear non-convex continuous functions

Mathematics Subject Classification ID

Graph theory (05C99) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Inventory, storage, reservoirs (90B05) Integer programming (90C10) Programming involving graphs or networks (90C35)

Review text

The problem of finding the absolute centre of a graph, which arises for example, in the selection of a site for an emergency-service centre, involves the global minimisation of certain piecewise-linear non-convex continuous functions. Using an algebraic characterization of the local minima of these functions, the author converts the continuous optimization problem into a combinatorial problem. An 0(n log n) algorithm is presented for solving this combinatorial problem.

Recommendations

• Locating an absolute center on graphs that are almost trees
• The absolute center of a network
• scientific article; zbMATH DE number 591341
• On the Solution Value of the Continuous p-Center Location Problem on a Graph
• An algorithm for finding the absolute center of a network

Cites work

• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• The Centers and Medians of a Graph

Cited in

(22)

• Group centre and group median of a network
• An algebra for piecewise-linear minimax problems
• An algorithm for finding the absolute center of a network
• Locating an absolute center on graphs that are almost trees
• Modelling and solving central cycle problems with integer programming.
• Maxpolynomial equations
• A comprehensive numerical algorithm for solving service points location problems
• scientific article; zbMATH DE number 4179135 (Why is no real title available?)
• scientific article; zbMATH DE number 3861213 (Why is no real title available?)
• scientific article; zbMATH DE number 4143134 (Why is no real title available?)
• scientific article; zbMATH DE number 4095237 (Why is no real title available?)
• On alternativep-center problems
• Biobjective center – balance graph location model^*
• scientific article; zbMATH DE number 591341 (Why is no real title available?)
• Optimization problems with unimodal functions in max-separabal constraints
• The absolute center of a network
• scientific article; zbMATH DE number 1786155 (Why is no real title available?)
• Global distribution center number of some graphs and an algorithm
• scientific article; zbMATH DE number 5030278 (Why is no real title available?)
• On the minimum diameter spanning tree problem
• The core of a graph
• The absolute center of a unicyclic network

This page was built for publication: The absolute centre of a graph

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