請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86968
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳健輝 | zh_TW |
dc.contributor.advisor | Gen-Huey Chen | en |
dc.contributor.author | 王柏元 | zh_TW |
dc.contributor.author | Po-Yuan Wang | en |
dc.date.accessioned | 2023-05-02T17:08:26Z | - |
dc.date.available | 2023-11-09 | - |
dc.date.copyright | 2023-05-02 | - |
dc.date.issued | 2022 | - |
dc.date.submitted | 2022-12-09 | - |
dc.identifier.citation | [1] M. S. Chang, S. Y. Hsieh, and G. H. Chen. Dynamic programming on distancehereditary graphs. In Proceedings of the International Symposium on Algorithms and Computation, pages 344–353. Springer, 1997.
[2] M. S. Chang, S. C. Wu, G. J. Chang, and H. G. Yeh. Domination in distancehereditary graphs. Discrete Applied Mathematics, 116(1-2):103–113, 2002. [3] L. Chen, C. H. Lu, and Z. B. Zeng. Hardness results and approximation algorithms for (weighted) paired-domination in graphs. Theoretical Computer Science, 410(47-49):5063–5071, 2009. [4] E. J. Cockayne, R. Dawes, and S. T. Hedetniemi. Total domination in graphs. Networks, 10(3):211–219, 1980. [5] M. Damian-Iordache and S. V. Pemmaraju. Hardness of approximating independent domination in circle graphs. In Proceedings of the International Symposium on Algorithms and Computation, pages 56–69. Springer, 1999. [6] M. Damian-Iordache and S. V. Pemmaraju. A (2+ ε)-approximation scheme for minimum domination on circle graphs. Journal of Algorithms, 42(2):255–276, 2002. [7] M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990. [8] S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387, 1998. [9] T. W. Haynes and P. J. Slater. Paired-domination in graphs. Networks, 32(3):199–206, 1998. [10] 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 on Discrete Mathematics, 15(4):488–518, 2002. [11] D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256–278, 1974. [12] J. M. Keil. The complexity of domination problems in circle graphs. Discrete Applied Mathematics, 42(1):51–63, 1993. [13] D. Kratsch and L. Stewart. Total domination and transformation. Information Processing Letters, 63(3):167–170, 1997. [14] C. C. Lin, K. C. Ku, and C. H. Hsu. Paired-domination problem on distancehereditary graphs. Algorithmica, 82(10):2809–2840, 2020. [15] H. G. Yeh and G. J. Chang. Weighted connected domination and steiner trees in distance-hereditary graphs. Discrete Applied Mathematics, 87(1-3):245–253, 1998. | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86968 | - |
dc.description.abstract | 支配問題是在給定的圖中尋找該圖點集的一個最小子集,使得圖上所有不屬於該子集的點,皆有至少一鄰居屬於該子集。完全支配問題則是在圖上尋找該圖點集的一個最小子集,使得圖上所有點皆有至少一鄰居屬於該子集。此二問題在圓形圖上皆為 NP-complete。Mirela 和 Sriram 為支配問題提出了一時間複雜度為 O(n^2) 的 8 倍近似演算法和時間複雜度為 O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) 的 (2+ε) 倍近似演算法,亦為完全支配問題提出了時間複雜度為 O(n^4+(6/ε)n^(⌈1+6/ε⌉)m) 的 (3+ε) 倍近似演算法。本篇論文則在此基礎上為完全支配問題提出了時間複雜度為 O(n+m) 的 10 倍近似演算法,並利用 Kratsch 和 Stewart 所提出的轉換方式提出時間複雜度為 O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) 的 (2+ε) 倍近似演算法。 | zh_TW |
dc.description.abstract | Given a graph, the domination problem is to find a minimum cardinality vertex subset of the graph, such that each vertex not in the subset has at least one neighbor in the subset. Similarly, the total domination problem is to find a minimum cardinality vertex subset of the graph, such that each vertex of the graph have at least one neighbor in the subset. These two problems are both NP-complete on circle graphs. Mirela and Sriram proposed an 8-approximation algorithm with O(n^2) time complexity and a (2+ε)-approximation algorithm with O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) time complexity for the domination problem. They also proposed a (3+ε)-approximation algorithm with O(n^4+(6/ε)n^(⌈1+6/ε⌉)m) time complexity for the total domination problem. Based on their results, we further proposed a 10-approximation algorithm for the total domination problem with O(n+m) time complexity in this thesis. With the transformation proposed by Kratsch and Stewart, we also proposed a (2+ε)-approximation algorithm with O(n^3+(6/ε)n^(⌈1+6/ε⌉)m) time complexity. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-05-02T17:08:26Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2023-05-02T17:08:26Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | 致謝 i
摘要 ii Abstract iii Contents iv List of Figures vi Chapter 1 Introduction 1 1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chapter 2 A 10-Approximation Algorithm 6 2.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Finding Cf1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Finding C2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Finding C3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Algorithm Correctness and Time Complexity . . . . . . . . . . . . . 10 2.5.1 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5.2 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Chapter 3 A (2 + ε)-Approximation Algorithm 16 3.1 A Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 A (2 + ε)-Approximation Algorithm . . . . . . . . . . . . . . . . . . 17 Chapter 4 Conclusion and Future Work 20 References 22 | - |
dc.language.iso | en | - |
dc.title | 圓形圖上完全支配問題的近似演算法 | zh_TW |
dc.title | Approximation Algorithms for the Total Domination Problem on Circle Graphs | en |
dc.type | Thesis | - |
dc.date.schoolyear | 111-1 | - |
dc.description.degree | 碩士 | - |
dc.contributor.coadvisor | 林清池 | zh_TW |
dc.contributor.coadvisor | Ching-Chi Lin | en |
dc.contributor.oralexamcommittee | 傅榮勝;張貴雲 | zh_TW |
dc.contributor.oralexamcommittee | Jung-Sheng Fu;Guey-Yun Chang | en |
dc.subject.keyword | 支配問題,完全支配問題,圓形圖,近似演算法, | zh_TW |
dc.subject.keyword | domination problem,total domination problem,circle graph,approximation algorithms, | en |
dc.relation.page | 23 | - |
dc.identifier.doi | 10.6342/NTU202210104 | - |
dc.rights.note | 未授權 | - |
dc.date.accepted | 2022-12-13 | - |
dc.contributor.author-college | 電機資訊學院 | - |
dc.contributor.author-dept | 資訊工程學系 | - |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-1.pdf 目前未授權公開取用 | 728.9 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。