1979/12/01 by O. Kariv, Oded Kariv, S. L. Hakimi · 1 citation
Business, Management and Accounting · Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary tree #Centroid #Combinatorics #Computational Geometry and Mesh Generation #Degree (music) #Discrete mathematics #Facility Location and Emergency Management #Gomory–Hu tree #Graph #K-ary tree #Mathematics #Median #Physics #Tree (set theory) #Tree structure #Vertex (graph theory)
paper · doi:10.1137/0137041
crossref issued 1979/12/01 · crossref published 1979/12/01 · crossref published-print 1979/12/01 · openalex publication_date 1979/12/01 · crossref created 2005/02/23 · crossref deposited 2019/01/28 · openalex created_date 2025/10/10 · crossref indexed 2026/07/30 · openalex updated_date 2026/07/30
It is shown that the problem of finding a p-median of a network is an NP-hard problem even when the network has a simple structure (e.g., planar graph of maximum vertex degree 3). However, results leading to efficient algorithms are presented when the network is a tree: In particular, we first show that a 1-median of a tree is identical to its w-centroid, and obtain Goldman’s O(n) algorithm for finding a 1-median of a tree out of more general considerations. Then, we present an algorithm which finds a p-median of a tree (for p > 1) in time O(n2 ⋅ p2 ).