請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56811
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
dc.contributor.author | Kuan-Lun Chen | en |
dc.contributor.author | 陳冠綸 | zh_TW |
dc.date.accessioned | 2021-06-16T05:49:58Z | - |
dc.date.available | 2015-09-01 | |
dc.date.copyright | 2014-09-04 | |
dc.date.issued | 2014 | |
dc.date.submitted | 2014-08-08 | |
dc.identifier.citation | [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing, Addison-Wesley Series in Computer Science and Information Processing.
[2] A. A. Bertossi and A. Gori. Total domination and irredundance in weighted interval graphs. SIAM J. Discrete Math., 1(3):317–327, 1988. [3] K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci., 13(3):335–379, 1976. Working Papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N. M., 1975). [4] G. J. Chang. The weighted independent domination problem is NP-complete for chordal graphs. Discrete Appl. Math., 143(1-3):351–352, 2004. [5] M.-S. Chang. Weighted domination of cocomparability graphs. Discrete Appl. Math., 80(2-3):135–148, 1997. [6] M.-S. Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput., 27(6):1671–1694 (electronic), 1998. [7] L. Chen, C. Lu, and Z. Zeng. A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inform. Process. Lett., 110(1):20–23, 2009. [8] L. Chen, C. Lu, and Z. Zeng. Labelling algorithms for paired-domination problems in block and interval graphs. J. Comb. Optim., 19(4):457–470, 2010. [9] T. C. E. Cheng, L. Kang, and E. Shan. A polynomial-time algorithm for the paired-domination problem on permutation graphs. Discrete Appl. Math., 157(2):262–271, 2009. [10] T. C. E. Cheng, L. Y. Kang, and C. T. Ng. Paired domination on interval and circular-arc graphs. Discrete Appl. Math., 155(16):2077–2086, 2007. [11] K. Choudhary, S. Margulies, and I. V. Hicks. A note on total and paired domination of Cartesian product graphs. Electron. J. Combin., 20(3):Paper 25, 9, 2013. [12] A. D’Atri and M. Moscarini. Distance-hereditary graphs, Steiner trees, and connected domination. SIAM J. Comput., 17(3):521–538, 1988. [13] E. M. Eschen. Circular-arc graph recognition and related problems. ProQuest LLC, Ann Arbor, MI, 1997. Thesis (Ph.D.)–Vanderbilt University. [14] E. M. Eschen and J. P. Spinrad. An O(n^2) algorithm for circular-arc graph recognition. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Austin, TX, 1993), pages 128–137. ACM, New York, 1993. [15] H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. J. Comput. System Sci., 30(2):209–221, 1985. [16] Z. Galil and G. F. Italiano. Data structures and algorithms for disjoint set union problems. ACM Comput. Surv., 23(3):319–344, Sept. 1991. [17] M. R. Garey and D. S. Johnson. Computers and intractability. W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences. [18] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Fundamentals of domination in graphs, volume 208 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York, 1998. [19] T. W. Haynes and P. J. Slater. Paired-domination in graphs. Networks, 32(3):199–206, 1998. [20] T. W. Haynes, P. J. Slater, and S. T. Hedetniemi. Domination in graphs : advanced topics / edited by teresa w. haynes, stephen t. hedetniemi, peter j. slater. 1997. Includes index. [21] S. Hedetniemi and R. Laskar. Topics on Domination. Annals of Discrete Mathematics. Elsevier Science, 1991. [22] M. A. Henning. A survey of selected recent results on total domination in graphs. Discrete Math., 309(1):32–63, 2009. [23] W. L. Hsu. O(M N) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM J. Comput., 24(3):411–439, 1995. [24] W. L. Hsu and T. H. Ma. Substitution decomposition on chordal graphs and applications. In ISA ’91. Algorithms (Taipei, 1991), volume 557 of Lecture Notes in Comput. Sci., pages 52–60. Springer, Berlin, 1991. [25] F.-T. Hu and J.-M. Xu. Total and paired domination numbers of toroidal meshes. J. Comb. Optim., 27(2):369–378, 2014. [26] R.-W. Hung. Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput. Syst., 50(4):721–738, 2012. [27] L. Kang, M. Y. Sohn, and T. C. E. Cheng. Paired-domination in inflated graphs. Theoret. Comput. Sci., 320(2-3):485–494, 2004. [28] H. Kaplan and Y. Nussbaum. A simpler linear-time recognition of circular-arc graphs. Algorithmica, 61(3):694–737, 2011. [29] N. Korte and R. H. Mohring. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput., 18(1):68–81, 1989. [30] E. Lappas, S. D. Nikolopoulos, and L. Palios. An O(n)-time algorithm for the paired domination problem on permutation graphs. European J. Combin., 34(3):593–608, 2013. [31] R. Laskar, J. Pfaff, S. M. Hedetniemi, and S. T. Hedetniemi. On the algorithmic complexity of total domination. SIAM J. Algebraic Discrete Methods, 5(3):420–425, 1984. [32] C. C. Lin and H. L. Tu. Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graphs. ArXiv e-prints, Jan. 2014. [33] C. L. Lu, M.-T. Ko, and C. Y. Tang. Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math., 119(3):227–250, 2002. [34] R. M. McConnell. Linear-time recognition of circular-arc graphs. Algorithmica, 37(2):93–147, 2003. [35] J. Pfaff, R. C. Laskar, and S. T. Hedetniemi. NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical report, 428, Department Mathematical Sciences, Clemson University, South Carolina, 1983. [36] H. Qiao, L. Kang, M. Cardei, and D.-Z. Du. Paired-domination of trees. J. Global Optim., 25(1):43–54, 2003. Dedicated to Professor J. B. Rosen on his 80th birthday. [37] G. Ramalingam and C. Pandu Rangan. A unified approach to domination problems on interval graphs. Inform. Process. Lett., 27(5):271–274, 1988. [38] G. Ramalingam and C. Pandu Rangan. New sequential and parallel algorithms for interval graph recognition. Inform. Process. Lett., 34(4):215–219, 1990. [39] O. Schaudt. Total domination versus paired domination. Discuss. Math. Graph Theory, 32(3):435–447, 2012. [40] K. Simon. A new simple linear algorithm to recognize interval graphs. In Computational geometry—methods, algorithms and applications (Bern, 1991), volume 553 of Lecture Notes in Comput. Sci., pages 289–308. Springer, Berlin, 1991. [41] A. Tucker. An efficient test for circular-arc graphs. SIAM J. Comput., 9(1):1–24, 1980. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56811 | - |
dc.description.abstract | 對於圖G = (V, E)而言,點集合S為圖G的支配點集合若且唯若S是V的子集合,且每個在V中的點若非同時在S中,則必與某些在S中之點相鄰。若圖G由一個支配點集合所生成的誘導子圖擁有完美配對,則此支配點集合也被稱為圖G之成對支配點集合。成對支配點問題即為在圖G上找出一個基數最小的成對支配點集合S且S為V之子集合。同時,如果圖G為一權重圖,也就是說在點集V與另一權重集合中存在一個一對一對應關係,則此問題將在圖G上找出一個成對支配點集合S,滿足S中所有點的全中相加為最小且S為V之子集合。
在此篇論文中,給予一個權重區段圖G,其對應之區段模型已可取得且所有邊界點已排序,且令n與m分別為點和邊之數量。我們首先提出一個可在O(n)時間內找出一個在G上之最小權重成對支配點集合的演算法。接著我們進一步設計另一個演算法,來找出一個在已可取得弧形模型的權重圓弧圖上的最小權重成對支配點集合。經由延伸我們已找出在權重區段圖上的結果,該演算法可整體在O(n+m)時間內完成。 | zh_TW |
dc.description.abstract | For a graph G = (V, E), a vertex set S is said to be a dominating set of G if and only if S $subseteq$ V and every vertex in V that not in S is adjacent to some vertices in S. The dominating set S is also said to be a paired-dominating set if the induced subgraph G[S] has a perfect matching. The paired-domination problem is to find the minimum-cardinality paired-dominating set S $subseteq$ V of G. And if G is a weighted graph, i.e. there exists a one-to-one corresponding between vertex set V and a weight set, then this problem is for finding a paired-dominating set S $subseteq$ V which sum of vertex weights in are minimum.
In this paper, given a weighted interval graph G with available interval model whose all endpoints are sorted, and let n and m be the vertex number and edge number, respectively. We first propose an O(n)-time algorithm for finding a minimum-weight paired-dominating set of G. Further, we design another algorithm for finding a minimum-weight paired-dominating set of weighted circular-arc graphs whose arc model is available, which can run in O(n+m) time totally by extending our results on weighted interval graph. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T05:49:58Z (GMT). No. of bitstreams: 1 ntu-103-R01944029-1.pdf: 516016 bytes, checksum: f03c7d5f19fabc80543e864ca5072e85 (MD5) Previous issue date: 2014 | en |
dc.description.tableofcontents | 1. Introduction p.1
1.1 Preliminaries p.1 1.2 Previous work p.6 2. Finding a minimum-weighted paired-dominating set on weighted interval graphs p.9 2.1 An algorithm p.9 2.2 Time complexity p.17 3. Finding a minimum-weighted paired-dominating set on weighted circular-arc graphs p.29 3.1 An algorithm p.29 3.2 Time complexity p.31 4. Conclusion p.35 Bibliography p.37 | |
dc.language.iso | en | |
dc.title | 權重區段圖與權重圓弧圖上的成對支配點問題 | zh_TW |
dc.title | Paired Domination on Weighted Interval Graphs and Circular-Arc Graphs | en |
dc.type | Thesis | |
dc.date.schoolyear | 102-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 林清池(Ching-Chi Lin) | |
dc.contributor.oralexamcommittee | 胡家正(Chia-Cheng Hu),周信宏(Hsin-Hung Chou) | |
dc.subject.keyword | 成對支配點問題,區段圖,圓弧圖,動態規劃, | zh_TW |
dc.subject.keyword | paired-domination problem,interval graphs,circular-arc graphs,dynamic programming, | en |
dc.relation.page | 41 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2014-08-08 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 503.92 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。