zbMATH — the first resource for mathematics

Efficient algorithms for the weighted 2-center problem in a cactus graph. (English) Zbl 1175.05125
Deng, Xiaotie (ed.) et al., Algorithms and computation. 16th international symposium, ISAAC 2005, Sanya, Hainan, China, December 19–21, 2005. Proceedings. Berlin: Springer (ISBN 3-540-30935-7/pbk). Lecture Notes in Computer Science 3827, 693-703 (2005).
Summary: 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^3 n)\) time algorithm is devised for its continuous version and showed that its discrete version is solvable in \(O(n\log^2n)\) 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 [B. Zmazek and J. Žerovnik, “The obnoxious center problem on weighted cactus graphs”, Discrete Appl. Math. 136, No. 2–3, 377–386 (2004; Zbl 1046.90036)]. In the worst case \(c\) is \(O(n)\).
For the entire collection see [Zbl 1098.68001].

05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI