Premium
An improved algorithm for the distance constrained p ‐center location problem with mutual communication on tree networks
Author(s) -
Tamir Arie
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20012
Subject(s) - center (category theory) , tree (set theory) , combinatorics , binary logarithm , simple (philosophy) , algorithm , tree network , computer science , upper and lower bounds , mathematics , time complexity , discrete mathematics , theoretical computer science , mathematical analysis , philosophy , chemistry , epistemology , crystallography
In a recent article Averbakh and Berman present an O ( p 3 + n 2 ) serial algorithm to solve the distance constrained p ‐center location problem with mutual communication on a tree network with n nodes. In this note we suggest two simple modifications leading to the improved (subquadratic in n ), O ( p 3 + p ( n + p )log 2 ( n + p )) complexity bound. We also present a new O ( p 2 n log n log( n + p )) algorithm for the discrete version of this problem. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 38–40 2004