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

DOI10.1137/0601043MaRDI QIDQ3960131zbMATH OpenOpenAlexFDO

Authors R. Chandrasekaran, Arie Tamir

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

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) 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)

Cites work

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

Cited in

(8)

• On search over rationals
• Efficient parallel algorithms for r-dominating set and p-center problems on trees
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
• Continuous bottleneck tree partitioning problems
• A finite algorithm for the continuousp-center location problem on a graph
• Fighting terrorism: how to position rapid response teams?
• From Chinese postman to salesman and beyond: shortest tour -covering all points on all edges
• The discrete p-dispersion problem

This page was built for publication: An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3960131)