Premium
The continuous p ‐median of a network
Author(s) -
Hansen Pierre,
Labbé Martine
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190509
Subject(s) - median , mathematics , combinatorics , point (geometry) , set (abstract data type) , enhanced data rates for gsm evolution , algorithm , tree (set theory) , discrete mathematics , computer science , geometry , artificial intelligence , programming language
The distance between an edge and a point of a network N is defined as the maximum distance from that point to any point on that edge. A continuous median of N is a point of N such that the sum of the distances between all edges and that point is minimum. A continuous p ‐median is a set of p points of N such that the sum for all edges of the distance to the closest poit of that set is minimum. It is shown that the set of vertices and middle points of edges always contaisn a continuous p ‐median. Therefore, powerful algorithms for the usual p ‐median problem can be brought to bear. Moreover, algorithms requiring O(m 2 ) operations in worst case for determining the set of all continuous and conditional continuous medians of N are obtained. A linear algorithm for the set of all continuous medians of a tree is also provided.