Efficient algorithms for center problems in cactus networks |
| |
Authors: | Boaz Ben-Moshe Binay Bhattacharya Qiaosheng Shi Arie Tamir |
| |
Affiliation: | 1. School of Computer Science, College of Judea and Samaria, Ariel, 44837, Israel;2. School of Computing Science, Simon Fraser University, Burnaby, BC, Canada, V5A 1S6;3. School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel |
| |
Abstract: | Efficient algorithms for solving the center problems in weighted cactus networks are presented. In particular, we have proposed the following algorithms for the weighted cactus networks of size n: an O(nlogn) time algorithm to solve the 1-center problem, and an O(nlog3n) time algorithm to solve the weighted continuous 2-center problem. We have also provided improved solutions to the general p-center problems in cactus networks. The developed ideas are then applied to solve the obnoxious 1-center problem in weighted cactus networks. |
| |
Keywords: | Facility location optimization Center problems Cactus networks |
本文献已被 ScienceDirect 等数据库收录! |
|