請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/59352完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝(Gen-Huey Chen) | |
| dc.contributor.author | Keng-Chu Ku | en |
| dc.contributor.author | 古耕竹 | zh_TW |
| dc.date.accessioned | 2021-06-16T09:21:15Z | - |
| dc.date.available | 2017-08-25 | |
| dc.date.copyright | 2017-08-25 | |
| dc.date.issued | 2017 | |
| dc.date.submitted | 2017-06-29 | |
| dc.identifier.citation | [1] S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics, 23:11–24, 1989.
[2] H. J. Bandelt and H. M. Mulder. Distance-hereditary graphs. Journal of Combinatorial Theory, Series B, 41:182–208, 1986. [3] A. A. Bertossi. Dominating sets for split and bipartite graphs. Information Processing Letters, 19:37–40, 1984. [4] A. A. Bertossi. Total domination in interval graphs. Information Processing Letters, 23:131–134, 1986. [5] T. Beyer, A. Proskurowski, S. Hedetniemi, and S. Mitchell. Independent domination in trees. In the Proceedings of SEICCGTC’77, pages 321–328, 1977. [6] K. S. Booth and J. H. Johnson. Dominating sets in chordal graphs. SIAM Journal on Computing, 11:191–199, 1982. [7] A. Brandstadt and D. Kratsch. On the restriction of some NP-complete graph problems to permutation graphs. In the Proceedings of FCT’85, Lecture Notes in Computer Science, volume 199, pages 53–62, 1985. [8] G. Chang. Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Applied Mathematics, 22:21–34, 1988. [9] G. J. Chang. Algorithmic aspects of domination in graphs. In Handbook of Combinatorial Optimization, pages 339–405. Springer-Verlag, New York, 2nd edition, 2013. [10] M. S. Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM Journal on Computing, 27:1671–1694, 1998. [11] M. S. Chang, S. Y. Hsieh, and G. H. Chen. Dynamic programming on distance-hereditary graphs. In the Proceedings of ISAAC’97, Lecture Notes in Computer Science, volume 1350, pages 344–353, 1997. [12] M. S. Chang, S. C. Wu, G. J. Chang, and H. G. Yeh. Domination in distance-hereditary graphs. Discrete Applied Mathematics, 116:103–113, 2002. [13] H. S. Chao, F. R. Hsu, and R. C. T. Lee. An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discrete Applied Mathematics, 102:159–173, 2000. [14] L. Chen, C. H. Lu, and Z. B. Zeng. A linear-time algorithm for paired-domination problem in strongly chordal graphs. Information Processing Letters, 110:20–23, 2009. [15] L. Chen, C. H. Lu, and Z. B. Zeng. Labeling algorithms for paired-domination problems in block and interval graphs. Journal of Combinatorial Optimization, 19:457–470, 2010. [16] T. C. E. Cheng, L. Kang, and C. T. Ng. Paired domination on interval and circular-arc graphs. Discrete Applied Mathematics, 155:2077–2086, 2007. [17] T. C. E. Cheng, L. Kang, and E. Shan. A polynomial time algorithm for the paired domination problem on permutation graphs. Discrete Applied Mathematics, 157:262–271, 2009. [18] E. Cockayne. A linear algorithm for the domination number of a tree. Information Processing Letters, 4:41–44, 1975. [19] C. J. Colbourn and L. K. Stewart. Permutation graphs: connected domination and Steiner trees. Discrete Mathematics, 86:179–189, 1990. [20] D. G. Corneil. Dominating sets in perfect graphs. Discrete Mathematics, 86:145–164, 1990. [21] D. G. Corneil and Y. Perl. Clustering and domination in perfect graphs. Discrete Applied Mathematics, 9:27–39, 1984. [22] A. D’Atri and M. Moscarini. Distance-hereditary graphs, Steiner trees, and connected domination. SIAM Journal on Computing, 17:521–538, 1988. [23] A. K. Dewdney. Fast Turing reductions between problems in NP 4. Technical Report 71, University of Western Ontario, 1981. [24] M. Farber. Independent domination in chordal graphs. Operations Research Letters, 1:134–138, 1982. [25] M. Farber. Domination, independent domination, and duality in strongly chordal graphs. Discrete Applied Mathematics, 7:115–130, 1984. [26] M. Farber. Domination in permutation graphs. Journal of Algorithms, 6:309–321, 1985. [27] C. P. Gabor, W. L. Hsu, and K. J. Supowit. Recognizing circle graphs in polynomial time. Journal of the ACM, 36:435–473, 1989. [28] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. [29] F. Gavril. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks, 3:261–273, 1973. [30] P. L. Hammer and F. Maffray. Completely separable graphs. Discrete Applied Mathematics, 27:85–99, 1990. [31] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Domination in Graphs: Advanced Topics. Marcel Dekker, New York, 1998. [32] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. [33] T. W. Haynes and P. J. Slater. Paired domination in graphs. Networks, 32:199–206, 1998. [34] S. T. Hedetniemi and R. Laskar. Bibliography on domination in graphs and some basic definitions of domination parameters. Discrete Mathematics, 86:257–277, 1990. [35] S. T. Hedetniemi and R. Laskar. Topics on Domination. Annals of Discrete Mathematics. North-Holland, Amsterdam, 1991. [36] E. Howorka. A characterization of distance-hereditary graphs. Quarterly Journal of Mathematics, 28:417–420, 1977. [37] S. Y. Hsieh, C. W. Ho, T. S. Hsu, M. T. Ko, and G. H. Chen. Characterization of efficiently parallel solvable problems on distance-hereditary graphs. SIAM Journal of Discrete Mathematics, 15:488–518, 2002. [38] W. L. Hsu and K. H. Tsai. Linear time algorithms on circular-arc graphs. Information Processing Letters, 40:123–129, 1991. [39] L. Kang. Variations of dominating set problem. In Handbook of Combinatorial Optimization, pages 3363–3394. Springer-Verlag, New York, 2nd edition, 2013. [40] J. M. Keil. Total domination in interval graphs. Information Processing Letters, 22:171–174, 1986. [41] J. M. Keil. The complexity of domination problems in circle graphs. Discrete Applied Mathematics, 42:51–63, 1993. [42] E. Lappas, S. D. Nikolopoulos, and L. Palios. An O(n)-time algorithm for the paired domination problem on permutation graphs. European Journal of Combinatorics, 34:593–608, 2013. [43] R. Laskar and J. Pfaff. Domination and irredundance in split graphs. Technical Report 430, Clemson University, 1983. [44] R. Laskar, J. Pfaff, S. M. Hedetniemi, and S. T. Hedetniemi. On the algorithmic complexity of total domination. SIAM Journal on Algebraic Discrete Methods, 5:420–425, 1984. [45] C. C. Lin and H. L. Tu. A linear time algorithm for paired domination on circular-arc graphs. Theoretical Computer Science, 591:99–105, 2015. [46] J. Pfaff, R. Laskar, and S. T. Hedetniemi. NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428, Clemson University, 1983. [47] H. Qiao, L. Kang, M. Cardei, and D. Z. Du. Paired domination of trees. Journal of Global Optimization, 25:43–54, 2003. [48] G. Ramalingam and C. P. Rangan. A unified approach to domination problems on interval graphs. Information Processing Letters, 27:271–274, 1988. [49] K. White, M. Farber, and W. Pulleyblank. Steiner trees, connected domination and strongly chordal graphs. Networks, 15:109–124, 1985. [50] H. G. Yeh and G. J. Chang. Weighted connected domination and Steiner trees in distance-hereditary graphs. Discrete Applied Mathematics, 87:245–253, 1998. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/59352 | - |
| dc.description.abstract | 一個圖 G 的點子集合 D 如果滿足「任意不在此集合中的點皆與 D 中至少一點相鄰」，則我們稱 D 為「支配點集合」；此外，如果 D 在 G 中的衍生子圖有一個完美配對，則我們稱 D 為「成對支配點集合」。「成對支配問題」指的是在給定圖中找出最小成對支配點集合的點個數。
一個圖 G 如果滿足「任意兩點在任意包含此兩點的連通衍生子圖中的距離皆相等」，則我們稱 G 為「保距圖」。在這篇論文中，我們提出了一個時間複雜度為 O(n^2) 且實作於分解樹上的動態規劃演算法來解決保距圖上的成對支配問題，其中 n 為給定圖的點個數。 一個圖 G 如果滿足「在圖 G 的點集合與一個圓形的弦集合之間存在一個一對一對應使得圖 G 中的兩點相鄰若且唯若此兩點在圓形中對應的兩弦相交」，則我們稱 G 為「圓形圖」。在這篇論文中，我們證明了圓形圖上的成對支配問題是 NP 完全問題。 | zh_TW |
| dc.description.abstract | A vertex subset D of a graph G is a dominating set if every vertex not in D is adjacent to at least a vertex in D; besides, if the subgraph of G induced by D has a perfect matching, then D is a paired dominating set. The paired domination problem is to find the size of a minimum paired dominating set for the given graph.
A graph G is distance-hereditary if each pair of vertices in any connected induced subgraph has the same distance as in G. In this thesis, we propose an O(n^2)-time dynamic programming algorithm that utilizes the decomposition tree to solve the paired domination problem on distance-hereditary graphs, where n is the number of vertices of the given graph. A graph G is a circle graph if there exists a one-to-one correspondence between the vertex set of G and the chord set of a circle, where two vertices of G are adjacent if and only if the corresponding chords of the circle intersect. In this thesis, we prove that the paired domination problem is NP-complete on circle graphs. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T09:21:15Z (GMT). No. of bitstreams: 1 ntu-106-R04922075-1.pdf: 3003625 bytes, checksum: 7086417f30ac8c0b041f6aec89a1b03f (MD5) Previous issue date: 2017 | en |
| dc.description.tableofcontents | 誌謝 i
摘要 ii Abstract iii 1 Introduction 1 1.1 The Paired Domination Problem . . . . . . . . . . . . . 1 1.2 Distance-Hereditary Graphs . . . . . . . . . . . . . . . 3 1.3 Circle Graphs . . . . . . . . . . . . . . . . . . . . . 6 2 Paired Domination in Distance-Hereditary Graphs 8 2.1 Notations, Definitions, and Properties . . . . . . . . . 8 2.2 Decomposition Trees . . . . . . . . . . . . . . . . . . 21 2.3 Algorithm Implementation . . . . . . . . . . . . . . . 23 2.4 Time/Space Complexity . . . . . . . . . . . . . . . . . 26 3 Paired Domination in Circle Graphs 29 3.1 Reduction from SATISFIABILITY . . . . . . . . . . . . . 29 3.2 Proof of NP-Completeness . . . . . . . . . . . . . . . 32 4 Conclusion 35 Bibliography 36 | |
| dc.language.iso | en | |
| dc.subject | 分解樹 | zh_TW |
| dc.subject | 保距圖 | zh_TW |
| dc.subject | 動態規劃 | zh_TW |
| dc.subject | NP 完全問題 | zh_TW |
| dc.subject | 圓形圖 | zh_TW |
| dc.subject | 成對支配問題 | zh_TW |
| dc.subject | NP-completeness | en |
| dc.subject | circle graph | en |
| dc.subject | decomposition tree | en |
| dc.subject | dynamic programming | en |
| dc.subject | distance-hereditary graph | en |
| dc.subject | paired domination | en |
| dc.title | 保距圖上的成對支配問題 | zh_TW |
| dc.title | Paired Domination in Distance-Hereditary Graphs | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 105-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 林清池(Ching-Chi Lin) | |
| dc.contributor.oralexamcommittee | 傅榮勝(Jung-Sheng Fu),張貴雲(Guey-Yun Chang) | |
| dc.subject.keyword | 成對支配問題,保距圖,動態規劃,分解樹,圓形圖,NP 完全問題, | zh_TW |
| dc.subject.keyword | paired domination,distance-hereditary graph,dynamic programming,decomposition tree,circle graph,NP-completeness, | en |
| dc.relation.page | 40 | |
| dc.identifier.doi | 10.6342/NTU201700970 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2017-06-29 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-106-1.pdf 未授權公開取用 | 2.93 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。