在本篇論文中，我們考慮了在排列圖上面的嫌惡設施物問題。我們先對於一般圖提出一個k-穩定的性質。之後在排列圖上我們將其分成九類，並證明某些種類的排列圖
分別有4-穩定，3-穩定，2-穩定的性質。最後對於那些滿足4-穩定的排列圖提出$O(n^4)$的演算法、滿足3-穩定的排列圖提出$O(n^3)$、滿足2-穩定的排列圖提出$O(n^2)$的演算法來解決嫌惡設施物問題。

In this thesis, we are concerned with the p-maxian problem in
permutation graphs. At first, we propose the concept of k-stable for
general graphs. We partition all permutation graphs into nine
classes, and prove that it is 4-stable for permutation graphs in
class 1, 3-stable in classes 2, 4 and 2-stable in class 5. Finally,
we propose algorithms for solving the p-maxian problem in
permutation graphs in class 1, permutation graphs in classes 2 and 4
and permutation graphs in class 5 in $O(n^4)$, $O(n^3)$ and $O(n^2)$
time, respectively.

[1] Aho, A., Hopcroft, J. and Ullman, J.: The Design and Analysis of Computer Algo-
rithms, Addison-Wesley, Reading, MA, 1974.
[2] Ahuja, R. K., Mehlhorn, K., Orlin, J. B. and Tarjan, R. E.: Faster algorithms for the
shortest path problem, J. ACM 37(2) (1990), 213-223.
[3] S. Bespamyatnikh, B. Bhattacharya, M. Keil, D. Kirkpatrick and M. Segal, Efficient
algorithms for centers and medians in interval and circular-arc graphs, Networks 29
(2002) 144-152.
[4] J. Bouttier, P. Di Francesco, E. Guitter, Geodesic distance in planar graphs, Nuclear
Physics B 663 (3) (2003): 535-567.
[5] R.E. Burkard, E. Cela, H. Dollani, 2-median in trees with pos/neg weights, Discrete
Appl. Math 105 (2000) 51-71.
[6] Yukun Cheng and Liying Kang, The p-maxian problem on interval graphs, Discrete
Applied Mathematics 2 (2010) 1986-1993.
[7] Danny Z. Chen, D. T. Lee, R. Sridhar and Chandra N. Sekharan , Solving the All-
Pair Shortest Path Query Problem on Interval and Circular-Arc Graphs, Networks
31 (1998) 249-257.
[8] Richard L. Church and Robert S. Garfinkel, Locating an Obnoxious Facility on a
Network, Transportation Science 12 (1978) 107-118.
[9] Derek G. Corneil, Stephan Olariu, and Lorna Stewart, Asteroidal Triple-Free Graphs,
SIAM J. Discrete Math 12 , 10 (1997), 399-430.
[10] Rainer E. Burkard, Jafar Fathali and Hossein Taghizadeh Kakhki, The p-maxian
problem on a tree, Operations Research Letters 35 (2007) 331-335.
[11] E. Erkut, T. Baptie, B. von Hohenbalken, The discrete p-maxian location problem,
Comput. Oper. Res. 17 (1990) 51-61.
[12] Floyd, R.: Algorithm 97: Shortest path, Comm. ACM 5(6) (1962), 345
[13] Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs , Academic
Pree, New York (1980).
[14] Frank Harary, A Characterization of Block Graphs, Canadian Mathematical Bulletin
6 (1963) 1-6.
[15] Liying Kang and Yukun Cheng, The p-maxian problem on block graphs, Journal of
Combinatorial Optimization 20 (2010) 131-141.
[16] O. Kariv and S.L.Hakimi, An Algorithmic Approach to Network Location Problems.
I. The p-Centers, SIAM Journal on Applied Mathematics 37 (1979) 513-538.
[17] O. Kariv and S.L.Hakimi, An Algorithmic Approach to Network Location Problems.
II. The p-Medians, SIAM Journal on Applied Mathematics 37 (1979) 539-560.
[18] J. Krarup, D. Pisinger and F. Plastria, Discrete location problems with push-pull
objectives, Discrete Applied Mathematics 123 (2002) 363-378.
[19] Sukumar Mondal, Madhumangal Pal, Tapan K. Pal, An Optimal Algorithm to Solve
the All-Pairs Shortest Paths Problem on Permutation Graphs, Journal of Mathemat-
ical Modelling and Algorithms 2 (2003) 57-65
[20] Pnueli, A., Lempel, A. and Even, S.: Transitive orientation of graphs and identifica-
tion of permutation graphs, Canad. J. Math. 23 (1971), 160-175.
[21] Seidel, R.: On the all pairs shortest path problem, In: Proc. 24th ACM STOC, ACM
Press, New York, 1992, pp. 745-749.
[22] A. Tamir, Obnoxious facility location on graphs, SIAM J. Discrete Math. 4 (1991)
550-567.
[23] S.S. Ting, A linear-time algorithm for maxisum facility location on tree networks,
Transp. Sci. 18 (1984) 76-84.
[24] B. Zelinka, Medians and peripherians of trees, Arch. Math. 4 (1968) 87-95.