Premium
Localizing 2‐medians on probabilistic and deterministic tree networks
Author(s) -
Mirchandani Pitu B.,
Oudjit Aissa
Publication year - 1980
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.3230100405
Subject(s) - median , probabilistic logic , tree (set theory) , deterministic algorithm , probabilistic analysis of algorithms , mathematics , computer science , simple (philosophy) , algorithm , mathematical optimization , combinatorics , statistics , philosophy , geometry , epistemology
Locating a single facility (the 1‐median problem) on a deterministic tree network is very efficiently solved by Goldman's algorithm. This paper explores the possibility of efficiently solving the 2‐median problem for both deterministic and probabilistic tree networks. Interesting properties (Theorems 1–4) are derived that relate the location of 1‐median to the location of pairs of 2‐medians. Two simple algorithms, the “Improved Link‐Deletion” algorithm for the deterministic case and the “Selective Enumeration” algorithm for the probabilistic case, are presented which somewhat improve existing methods to determine 2‐medians on tree networks.