TY - GEN
T1 - Efficient algorithms for the weighted 2-center problem in a cactus graph
AU - Ben-Moshe, Boaz
AU - Bhattacharya, Binay
AU - Shi, Qiaosheng
PY - 2005
Y1 - 2005
N2 - In this paper, we provide efficient algorithms for solving the weighted center problems in a cactus graph. In particular, an O(n log n) time algorithm is proposed that finds the weighted 1-center in a cactus graph, where n is the number of vertices in the graph. For the weighted 2-center problem, an O(n log 3n) time algorithm is devised for its continuous version and showed that its discrete version is solvable in O(n log2n) time. No such algorithm was previously known. The obnoxious center problem in a cactus graph can now be solved in O(n log 3n). This improves the previous result of O(cn) where c is the number of distinct vertex weights used in the graph [8]. In the worst case c is O(n).
AB - In this paper, we provide efficient algorithms for solving the weighted center problems in a cactus graph. In particular, an O(n log n) time algorithm is proposed that finds the weighted 1-center in a cactus graph, where n is the number of vertices in the graph. For the weighted 2-center problem, an O(n log 3n) time algorithm is devised for its continuous version and showed that its discrete version is solvable in O(n log2n) time. No such algorithm was previously known. The obnoxious center problem in a cactus graph can now be solved in O(n log 3n). This improves the previous result of O(cn) where c is the number of distinct vertex weights used in the graph [8]. In the worst case c is O(n).
UR - https://www.scopus.com/pages/publications/33744950132
U2 - 10.1007/11602613_70
DO - 10.1007/11602613_70
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:33744950132
SN - 3540309357
SN - 9783540309352
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 693
EP - 703
BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005
Y2 - 19 December 2005 through 21 December 2005
ER -