2026-08-16T13:18:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6029 2024-03-06T10:37:29Z ddc:004 open_access

The p-Center Problem in Tree Networks Revisited Banik, Aritra Bhattacharya, Binay Das, Sandip Kameda, Tsunehiko Song, Zhao Facility location p-center parametric search tree network sorting network We present two improved algorithms for weighted discrete p-center problem for tree networks with n vertices. One of our proposed algorithms runs in O(n*log(n) + p*log^2(n) * log(n/p)) time. For all values of p, our algorithm thus runs as fast as or faster than the most efficient O(n*log^2(n)) time algorithm obtained by applying Cole's [1987] speed-up technique to the algorithm due to Megiddo and Tamir [1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in O(n*log(n) + p^2*log^2(n/p)) time, and when p=O(sqrt(n)) it is faster than Megiddo and Tamir's O(n*log^2(n) * log(log(n))) time algorithm [1983]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aritra Banik and Binay Bhattacharya and Sandip Das and Tsunehiko Kameda and Zhao Song 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.6 urn:nbn:de:0030-drops-60296 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.6 eng https://creativecommons.org/licenses/by/3.0/legalcode