Obnoxious centers in graphs

ABSTRACT

We consider the problem of finding obnoxious centers in graphs. For arbitrary graphs with n vertices and m edges, we give a randomized algorithm with O(n log² n + m log n) expected time. For planar graphs, we give algorithms with O(n log n) expected time and O(n log³ n) worst-case time. For graphs with bounded treewidth, we give an algorithm taking O(n log n) worst-case time. The algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs.

REFERENCES

• 1: B. Ben-Moshe, B. K. Bhattacharya, and Q. Shi. Efficient algorithms for the weighted 2-center problem in a cactus graph. In Algorithms and Computation: ISAAC 2005, volume 3827 of Lecture Notes in Computer Science, pages 693--703. Springer-Verlag, 2005.
• 2: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 3: Hans L. Bodlaender, Treewidth: Algorithmoc Techniques and Results, Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, p.19-36, August 25-29, 1997
• 4: Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, v.209 n.1-2, p.1-45, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00228-4]
• 5: Hans L. Bodlaender , Torben Hagerup, Parallel Algorithms with Optimal Speedup for Bounded Treewidth, SIAM Journal on Computing, v.27 n.6, p.1725-1746, Dec. 1998 [doi>10.1137/S0097539795289859]
• 6: Rainer E. Burkard , Helidon Dollani , Yixun Lin , Günter Rote, The Obnoxious Center Problem on a Tree, SIAM Journal on Discrete Mathematics, v.14 n.4, p.498-509, 2001 [doi>10.1137/S0895480198340967]
• 7: Shiva Chaudhuri , Christos D. Zaroliagis, Shortest paths in digraphs of small treewidth. Part II: optimal parallel algorithms, Theoretical Computer Science, v.203 n.2, p.205-223, Aug. 28, 1998
• 8: S. Chaudhuri and C. D. Zaroliagis. Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica, 27:212--226, 2000.
• 9: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• 10: Jittat Fakcharoenphol , Satish Rao, Planar graphs, negative weight edges, shortest paths, and near linear time, Journal of Computer and System Sciences, v.72 n.5, p.868-889, August 2006 [doi>10.1016/j.jcss.2005.05.007]
• 11: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 12: M. J. Katz, K. Kedem, and M. Segal. Improved algorithms for placing undesirable facilities. Computers and Operations Research, 29:1859--1872, 2002.
• 13: Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 14: R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177--189, 1979.
• 15: N. Megiddo. Combinatorial optimization with rational objective functions. Math. Oper. Res, 4(4):414--424, 1979.
• 16: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 17: N. Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM J. Comput., 12:759--776, 1983.
• 18: Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
• 19: Bruce A. Reed, Finding approximate separators and computing tree width quickly, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.221-228, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129734]
• 20: Arie Tamir, Improved complexity bounds for center location problems on networks by using dynamic data structures, SIAM Journal on Discrete Mathematics, v.1 n.3, p.377-396, Aug. 1988 [doi>10.1137/0401038]
• 21: Arie Tamir, Obnoxious facility location on graphs, SIAM Journal on Discrete Mathematics, v.4 n.4, p.550-567, Nov. 1991 [doi>10.1137/0404048]
• 22: A. Tamir. Locating two obnoxious facilities using the weighted maximin criterion. Operations Research Letters, 34:97--105, 2006.
• 23: Blaz Zmazek , Janez Žerovnik, The obnoxious center problem on weighted cactus graphs, Discrete Applied Mathematics, v.136 n.2-3, p.377-386, 15 February 2004 [doi>10.1016/S0166-218X(03)00452-9]