本論文探討的是在具權重之梯形圖上解史坦那連結問題。梯形圖中的梯形(Trapezoid) iT 是由四個角ai, bi, ci, di所構成。在梯形表示法(Trapezoid diagram)中，ai和bi座落在上方水平線，ci和di座落在下方水平線。如果一個無向圖G(V,E)可以用梯形表示法表示，意即圖G上的每個點在梯形表示法中皆對應其中的一個梯形，且在圖G上的每一條邊(vi,vj),表示在梯形表示法中與其相對應的梯形 Ti和Tj有交集，則我們就稱圖G為梯形圖(Trapezoid graph)。
給定一具權重的梯形圖G(V,E)，令R包含於V與S包含於V-R分別表示圖G的一組目標點集合(Target set)與史坦那集合(Steiner set)，若存在一組點集合I包含於S使得I聯集R所形成的誘導子圖(Induced subgraph)為連通圖(Connected graph)，則我們稱集合I中的節點為史坦那節點(Steiner vertices)。令I0表示集合S的一組史坦那節點，若集合I0中所有點的權重值加總為所有史坦那節點集合I的最小值，則我們稱I0為minimum weighted steiner vertex set。在本篇論文中，我們將針對(點)具權重的梯形圖，提出O(nloglogn)的演算法求minimum weighted steiner vertex set。

In this thesis, we are concerned with the steiner connected problem on weighted trapezoid graphs. A trapezoid Ti is defined by four corner points  ai, bi, ci, di such that ai and bi are lying on the top line and ci and di are lying on the bottom line of the trapezoid diagram. A graph G(V,E) is a trapezoid graph if it can be represented by a trapezoid diagram such that each vertex v stands for a trapezoid T in the trapezoid diagram and (vi,vj) E, if and only if two trapezoids Ti and Tj intersect.
Given a weighted trapezoid graph G(V,E) , let R V and S V-R be target vertices and steiner set, respectively. If there exists a set of vertices I S, such that I U R induces a connected subgraph, then we call that these vertices of I steiner vertices. Let I0 be a set of steiner vertices with respect to R and S. We say that I0 is the minimum weighted steiner vertex set if the sum of the weights of all vertices in I0 is minimum. In this thesis, we present an O(nloglogn)-time algorithm for finding the minimum weighted steiner vertex set on weighted trapezoid graphs.

[1] K. Arvind and C. Pandu Regan, “Connected domination and Steiner set on weighted permutation graphs”, Information Processing Letters, Vol. 41, pp. 215-220 (1992).
[2] G. Agnarssona, Á. S. Egilssonb and M. M. Halldórssonc, “Vertex coloring acyclic digraphs and their corresponding hypergraphs”, Discrete Applied Mathematics, Vol. 156, pp. 1918-1928 (2008).
[3] H. Breu and D.G. Kirkpatrick, “Algorithms for dominating and Steiner set problems in cocomparability graphs”, manuscript (1993).
[4] G. J. Chang, J. Wu and X. Zhu, Rainbow domination on trees, Discrete Applied Mathematics, Vol. 158, pp. 8-12 (2010).
[5] C. Chen and R.C.T. Lee, “The weighted perfect domination problem”, Information Processing Letters, Vol. 35, pp. 295-299 (1990).
[6] C. J. Colbourn and L. K. Stewant, “Permutation graphs: connected domination and Steiner trees”, Discrete Mathematics, Vol. 86, pp. 145-164 (1990).
[7] D. G. Corneil and P. A. Kamula, “Extension of permutation and interval graphs”, Proceedings of the 18th Southeast Conference on Combinatorics, Graph Theory and Computing, pp. 267-276(1987).
[8] D. G. Corneil and L.K. Stewart, “Dominating sets in perfect graphs”. Discrete Mathematics, Vol. 86, pp. 179-189 (1990).
[9] I. Dagan, M. C. Golumbic and R. Y. Pinter, “Trapezoid graphs and their coloring”, Discrete Applied Mathematics, Vol. 21, pp. 35-46 (1988).
[10] A. D`Atri, and M. Mascarini, “Distance hereditary graphs, Steiner trees and connected domination”, SIAM Journal on Computing, Vol. 17, pp. 521-538 (1988).
[11] S. Felsner, R. Müller and L. Wernisch, “Trapezoid graphs and generalizations, geometry and algorithms”, Discrete Applied Mathematics, Vol. 74, pp. 13-32 (1997).
[12] M.L. Fredman and R.E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM, Vol. 34, pp. 596-615 (1987).
[13] M.C. Golumbic, Algorithmic graph theory and perfect graphs, Academic press, New York, (1980).
[14] I. Holyer, The NP-completeness of edge-coloring, SIAM Journal on Computing, Vol. 10, pp. 718-720 (1981).
[15] D. S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms, Vol. 6, pp. 434-451(1985).
[16] E.Kohler, “Connected domination and dominating clique in trapezoid graphs”. Discrete Applied Mathematics, Vol. 99, pp. 91-110 (2000).
[17] Y. D. Liang, “Dominations in trapezoid graphs”, Information Processing Letters, Vol. 52, pp. 309-315 (1994).
[18] Y. D. Liang, “Steiner set and connected domination in trapezoid graphs”, Information Processing Letters, Vol. 56, pp. 101-108 (1995).
[19] Y.L. Lin, “Fast algorithms for independent domination and efficient domination in trapezoid graphs”, Proceedings of ISAAC’98, Lecture Notes in Computer Science, Vol. 1533, pp. 267-276 (1998).
[20] T. H. Ma and J.P. Spinrad, “On the 2-chain subgraph cover and related problems”, Journal of Algebra, Vol. 17, pp. 251-268 (1994).
[21] S. Mondal, M. Pal and T. K. Pal, “Optimal sequential and parallel algorithms to compute a Steiner tree on permutation graphs”, International Journal of Computer Mathematics, Vol. 80, No. 8, pp. 939-945 (2003).
[22] R. Ramamurthi and D. B. West, “Maximum face-constrained coloring of plane graphs”, Discrete Mathematics, Vol. 274, pp. 233-240 (2004).
[23] C. Rhee, Y. D. Liang, S. K. Dhall and S. Lakshmivarahan, “An O(m+n) algorithm for finding minimum weight dominating set in permutation graphs”, SIAM Journal on Computing, Vol. 25, No. 2, pp. 404-419 (1996).
[24] Y. Tsai, Y. Lin and F.R. Hsu, “Efficient algorithms for the minimum connected domination on trapezoid graphs”, Information Sciences, Vol. 177, pp. 2405-2417 (2007).
[25] P. van Emde Boas, “Preserving order in a forest in less than logarithmic time and linear space”, Information Processing Letters, Vol. 6, pp. 80-82 (1977).
[26] K. White, M. Farber and W.R. Pulleyblank, “Steiner trees, connected domination and strongly chordal graphs”, Networks, Vol. 15, pp. 109-124 (1985).