Localizing 2‐medians on probabilistic and deterministic tree networks

Pitu B. Mirchandani, Aissa Oudjit

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)329-350
Number of pages22
Issue number4
StatePublished - 1980
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this