التفاصيل البيبلوغرافية
| العنوان: |
Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph. |
| المؤلفون: |
Xiaotie Deng, Dingzhu Du, Ben-Moshe, Boaz, Bhattacharya, Binay, Shi, Qiaosheng |
| المصدر: |
Algorithms & Computation (9783540309352); 2005, p693-703, 11p |
| مستخلص: |
In this paper, we provide efficient algorithms for solving the weighted center problems in a cactus graph. In particular, an O(n logn) 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 log3n) 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 log3n). 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). [ABSTRACT FROM AUTHOR] |
|
Copyright of Algorithms & Computation (9783540309352) is the property of Springer eBooks and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
