Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Banik, Aritra; Bhattacharya, Binay; Das, Sandip; Kameda, Tsunehiko; Song, Zhao http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-60296
URL:

; ; ; ;

The p-Center Problem in Tree Networks Revisited

pdf-format:


Abstract

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].

BibTeX - Entry

@InProceedings{banik_et_al:LIPIcs:2016:6029,
  author =	{Aritra Banik and Binay Bhattacharya and Sandip Das and Tsunehiko Kameda and Zhao Song},
  title =	{{The p-Center Problem in Tree Networks Revisited}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6029},
  URN =		{urn:nbn:de:0030-drops-60296},
  doi =		{10.4230/LIPIcs.SWAT.2016.6},
  annote =	{Keywords: Facility location, p-center, parametric search, tree network, sorting network}
}

Keywords: Facility location, p-center, parametric search, tree network, sorting network
Seminar: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI