臺灣博碩士論文加值系統

This thesis addresses the p-Center problem with some practical constraints. Let G(V, E, W) denote a graph with n-vertex-set V and m-edge-set E in which W is a function mapping each edge e to a positive distance W(e). The traditional p-Center problem is to locate some kind of facilities at p vertices of G to minimize the maximum distance between any vertex and the nearest facility corresponding to that vertex. This thesis considers some more practical constraints. We first require that the p vertices in which the facilities are located must be connected, i.e., the subgraph induced by the p facility vertices must be connected. The resulting problem is called the Connected p-Center problem (the CpC problem). Meanwhile, we deal with further restriction in which all vertices in F cannot be included in any feasible solution, for any given subset F of V. The vertices in F are called forbidden vertices and the problem is called the Forbidden Connected p-Center problem (the FCpC problem). We first show that the CpC problem is NP-Hard on bipartite graphs. Second, O(n)-time and O(pn)-time algorithms for the CpC problem on trees and 3-cactus graphs are proposed, respectively. Finally, the algorithmic results are extended to the FCpC problem on trees and 3-cactus graphs. The time-complexities remain O(n) and O(pn), respectively.

Table of Contents……………………………………………………………………...2
Table of Graphs………………………………………………………………………..3
Acknowledgment……………………………………………………………………...5
Abstract………………………………………………………………………………..6
1. Introduction………………………………………………………………………7
2. The Connected p-Center Problem on Bipartite Graphs…………………………11
3. The Connected p-Center Problem on Trees…………………………………….15
4. The Connected p-Center Problem on 3-Cactus Graphs………………………...23
5. The Forbidden Connected p-Center Problem on Trees…………………………34
6. The Forbidden Connected p-Center Problem on 3-Cactus Graphs……………..41
7. Conclusions and Future Research Directions…………………………………...47
8. References………………………………………………………………………49

References
1.Abdelaziz F., “1-center problem on the plane with uniformly distributed demand points”, Operations Research Letters, Vol. 34, Iss. 3, 264-268, 2006.
2.Alain B. and Marie-Christine C., “Solving the uncapacited plant location problem on trees”, Discrete Applied Mathematics, Vol. 49, Iss. 1-3, 51-59, 1994.
3.Bar-Ilan J and Peleg D, “Approximation algorithms for selecting network centers”, in Proceedings of workshop on algorithms and data structures, 343–354, 1991.
4.Bespamyatnikh S, Bhattacharya B, Keil M, Kirkpatrick D., and Segal M., “Efficient algorithms for centers and medians in interval and circular-arc graphs”, Networks, Vol. 39, 144–152, 2002.
5.Bla Z. and Janez ., “The obnoxious center problem on weighted cactus graphs,” Discrete Applied Mathematics, Vol. 136, Iss. 2-3, 377-386, 2004.
6.Brandeau M. L. and Chiu S. S., “An overview of representative problems in location research”, Management Science, 35(6), 645-674,1989.
7.Burkard R. E. and Dollani H., “Center problems with pos/neg weights on trees”, European Journal of Operational Research, Vol. 145, Iss. 3, 483-495, 2003.
8.Rangan C. P. and Govindan R., “An O(nlogn) algorithm for a maxmin location problem”, Discrete Applied Mathematics, Vol. 36, Iss. 2, 203-205, 30 April 1992.
9.Chenga T. C. E., Kang Liying, and Ng C. T. (to appear),” An improved algorithm for the p-center problem on interval graphs with unit lengths”, Computers & Operation Research.
10.Daskin M. S., Networks and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons, Inc., New York, 1995.
11.F. Aykut Özsoy and Mustafa Ç. Pınar, “An exact algorithm for the capacitated vertex p-center problem”, Computers & Operations Research, Vol. 33, Iss. 5, 1420-1436, May 2006.
12.Frederickson G., “Parametric search and locating supply centers in trees”, in Proceedings of workshop on algorithms and data structures, 299–319, 1991.
13.Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Bell Laboratories, Murray Hill, Freeman & Co., N. J, 1978.
14.Goldman, A. J., ”Optimal location in simple network”, Transportation Science, Vol. 5, 212-221, 1971.
15.Golumbic M. C., Algorithmic graph theory and perfect graphs, Academic Press, Inc., New York, 1980.
16.Hakimi S. L., “Optimum location of switching centers and the absolute centers and median of a graph”, Operations Research, Vol. 12, 450-459, 1964.
17.Hakimi S. L., “Optimal distribution of switching center in a communication network and some related graph theoretic problem,” Operations Research, 13, 462-475,1965.
18.Hiroshi N., Toshimasa I., and Hiro I., “Minimum cost source location problem with vertex-connectivity requirements in digraphs”, Information Processing Letters, Vol. 80, Iss. 6, 287-293, 2001
19.Hochbaum D, and Shmoys D. B., “A unified approach to approximation algorithms for bottleneck problems”, Journal of the ACM, Vol. 33, 533–550, 1986.
20.Hsu V. N., Lowe T. J., Tamir A., “Structured p-facility location problems on the line solvable in polynomial time”, Operations Research Letters, Vol. 21, 159–164, 1997.
21.Huang P. H., Tsai Y. T., and Tang C. Y., “A fast algorithm for the alpha-connected two-center decision problem “, Information Processing Letters, Vol. 85, Iss. 4, 2005-210, 2003.
22.Kariv O, and Hakimi S. L., “An algorithmic approach to network location problems I: the p-centers”, SIAM Journal of Applied Mathematics, Vol. 37, 514–538, 1979.
23.Labbe M, Peeters D, and Thisse J. F., “Location on networks.” In: Ball M, Magnanti T, Francis RL, editors. Handbooks in operations research and management science. Amsterdam: Elsevier, 1995.
24.Lan Y. F., Wang Y. L., Suzuki H., “A linear-time algorithm for solving the center problem on weighted cactus graphs”, Information Processing Letters, Vol. 71, 205-212, 1999.
25.Olariu S., “A simple linear-time algorithm for computing the center of an interval graph”, International Journal of Computer Mathematics, Vol. 24, 121–128, 1990.
26.Pierre Hansen Martine Labbé Brigitte Nicolas, “The continuous center set of a network”, Discrete Applied Mathematics, Vol. 30, Iss. 2-3, 181-195, 1991.
27.Tamir A., “Improved complexity bounds for center location problems on networks by using dynamic data structures”, SIAM Journal of Discrete Mathematics, Vol. 1, 377–396, 1988.
28.Tansel B. C., Francis R. L., Lowe T. J. “Location on networks: a survey—Part I: the p-center and p-median problems.” Management Science, Vol. 29, Iss. 4, 482-497, 1983.