臺灣博碩士論文加值系統

此論文介紹了傳統圖上p 中心頂點問題一個新的且有趣的變化，我們叫作完滿p 中心頂點問題(the TpC problem)，簡稱完滿p 中心問題。它的目標為在一個頂點與邊均有權重的圖G(V, E, w, l)中找出一組p 個頂點Q，使得所有不在Q中的頂點存取Q 中最近頂點的權重距離最大者要最小，同時Q 中頂點之誘發子圖不可有孤立的頂點。本研究中，我們專注在由中心頂點所誘發的子圖剛好由k個連通單元所構成，我們叫作k單元完滿p 中心問題。我們首先證明k單元完滿p 中心問題在平面圖及二裂圖上邊長度為{1, 2}時為NP-困難的。同時，也設計出O(pnlogn)的演算法路徑上分別在解決k單元p 中心問題及k單元完滿p 中心問題。之後在具有禁選頂點的圖，我們證明了在路徑上這兩個問題仍可在O(pnlogn)的時間解決。

This thesis introduces a new useful and interesting variation of the traditional p-Center problem on graphs, called the Total p-Center problem (the TpC problem). Its goal is to find a p-vertex set Q of a graph G(V, E, w, l) with weights on vertices and lengths on edges such that the maximum weighted access distance of all vertices not in Q to their nearest vertices in Q is minimized, and the induced subgraph by Q cannot include any isolated vertex. In this research, we concentrate on the situation that the induced subgraph by the center vertices is formed by exactly k components, called the k-Com TpC problem. We first show that the k-Com TpC problem on planar graphs and bipartite graphs with {1, 2}-edge-length is NP-hard, respectively. Meanwhile, O(pnlogn) time algorithms are proposed for the 2-Com p-Center problem and the 2-Com TpC problem on paths, respectively. After then, on graphs with forbidden vertices, we show that both 2-Com p-Center problem and the 2-Com TpC problem on paths are also O(pnlogn) time solvable.

Table of Contents
Table of Contents --------------------------------------------------------------------------------1
Table of Figures ---------------------------------------------------------------------------------2
誌謝 ---------------------------------------------------------------------------------------------3
摘要 ---------------------------------------------------------------------------------------------4
Abstract -----------------------------------------------------------------------------------------5
1. Introduction-----------------------------------------------------------------------------------6
2. Some NP-Hard Results -------------------------------------------------------------------------12
3. Efficient Algorithms on Paths ----------------------------------------------------------------17
4. Extensions to Graphs with Forbidden Vertices -------------------------------------------------26
5. Conclusion -----------------------------------------------------------------------------------34
References --------------------------------------------------------------------------------------35

[1]B. Ben-Moshe, B. Bhattacharya, Q. Shi, A. Tamir (2007), “Efficient Algorithms for Center Problems in Cactus Graphs”, Theoretical Computer Science, Vol. 378, 237-252.
[2]S. Bespamyatnikh, B. Bhattacharya, M. Keil, D. Kirkpatrick, and M. Segal (2002), “Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs”, Networks, Vol. 39, 144-152.
[3]R. E. Burkard and H. Dollani (2003), “Center Problems with Pos/Neg Weights on Trees”, European Journal of Operational Research, Vol. 145, 485-495.
[4]T. C. E. Cheng, L. Kang, and C. T. Ng. (2007), “An Improved Algorithm for the p-Center Problem on Interval Graphs with Unit Lengths”, Computers & Operations Research, Vol. 34, pp. 2215-2222.
[5]M. S. Daskin (2008), “What You Should Know about Location Modeling”, Naval Research Logistics, Vol. 55, 283-294.
[6]M. S. Daskin, Networks and Discrete Location, Models, Algorithms, and Applications, John Wiley & Sons, Inc., New York, 1995
[7]S. Durocher and C. Paul, "Kinetic maintenance of mobile k-centres on trees", Discrete Applied Mathematics 157 (7), 1432-1446 (2009).
[8]S. Durocher, K. R. Jampani, A. Lubiw, and L. Narayanan, "Modelling gateway placement in wireless networks: Geometric k-centres of unit disc graphs", Computational Geometry 44 (5), 286-302 (2011).
[9]G. N. Frederickson (1991), “Parametric Search and Locating Supply Centers in Trees”, in Proceedings of Workshop on Algorithms and Data Structures, 299–319.
[10]M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Bell Laboratories, Murray Hill, Freeman & Co., N. J. ,1978
[11]M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, Inc., New York. 1980
[12]O. Kariv, S. L. Hakimi (1979), “An Algorithmic Approach to Network Location Problems I: the p-Centers”, SIAM Journal of Applied Mathematics, Vol. 37, 514–538.
[13]Y-F Lan, Y-L Wang, and H. Suzuki (1999), “A Linear-Time Algorithm for Solving the Center Problem on Weighted Cactus Graphs”, Information Processing Letters, Vol. 71, 205–212.
[14]S. Olariu (1990), “A Simple Linear-Time Algorithm for Computing the Center of an Interval Graph”, International Journal of Computer Mathematics, Vol. 24, 121–128.
[15]J. Puerto, A. Tamir, J. A. Mesa, and D. Perez-Brito, "Center location problems on tree graphs with subtree-shaped customers," Discrete Applied Mathematics 156 (15), 2890-2910 (2008).
[16]C. S. ReVelle, H. A. Eiselt, and M. S. Daskin (2008), “A Bibliography for Some Fundamental Problem Categories in Discrete Location Science”, European Journal of Operational Research, Vol. 184, 817–848.
[17]A. Tamir (1988), “Improved Complexity Bounds for Center Location Problems on Networks by using Dynamic Data Structures”, SIAM Journal on Discrete Mathematics, Vol. 1, 377–396.
[18]B. C. Tansel, R. L. Francis, and T. J. Lowe (1983), “Location on Networks: A Survey, Part I: The p-Center and p-Median Problems”, Management Science, Vol. 29, 482–497.
[19]W. C-K Yen and C-T Chen (2007), “The p-Center Problem with Connectivity Constraint”, Applied Mathematical Sciences, Vol. 1, 1311–1324.