Back to Search Start Over

The continuous center set of a network

Authors :
Martine Labbé
Brigitte Nicolas
Pierre Hansen
HEC Montréal (HEC Montréal)
Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX)
Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)
Graphes et Optimisation Mathématique [Bruxelles] (GOM)
Université libre de Bruxelles (ULB)
Fortz, Bernard
Source :
Discrete Applied Mathematics, Discrete Applied Mathematics, Elsevier, 1991, 30, pp.181-195
Publication Year :
1991
Publisher :
HAL CCSD, 1991.

Abstract

The continuous radius of a network N is the minimum for all points of N (i.e., vertices or points on edges) of the maximum distance from x to any other point y of N.Any point of N remote from any other point of a distance not exceeding the continuous radius is a continuous center. The continuous center set of N is the union of all continuous centers.Properties of the continuous center set are studied and an algorithm is given to determine it, which requires O(m2log m) time and O(m) space in the worst case, m being the number of edges of N.

Details

Language :
English
ISSN :
0166218X
Database :
OpenAIRE
Journal :
Discrete Applied Mathematics, Discrete Applied Mathematics, Elsevier, 1991, 30, pp.181-195
Accession number :
edsair.doi.dedup.....f3447cc325daabb853aff6c9bbf5eefc