An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree

DOI10.1137/0601043zbMath0496.68045OpenAlexW1963869288MaRDI QIDQ3960131

Arie Tamir, R. Chandrasekaran

Publication date: 1980

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0601043

zbMATH Keywords

center locationlocating p facilities on a tree network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Applications of graph theory to circuits and networks (94C15)

Related Items

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, A finite algorithm for the continuousp-center location problem on a graph, The discrete p-dispersion problem, On search over rationals, Efficient parallel algorithms for r-dominating set and p-center problems on trees, Continuous bottleneck tree partitioning problems

Cites Work

• Time bounds for selection
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort
• On the connectivity of maximal planar graphs