請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40158完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Yen-Yi Lin | en |
| dc.contributor.author | 林晏禕 | zh_TW |
| dc.date.accessioned | 2021-06-14T16:41:57Z | - |
| dc.date.available | 2008-08-04 | |
| dc.date.copyright | 2008-08-04 | |
| dc.date.issued | 2008 | |
| dc.date.submitted | 2008-08-01 | |
| dc.identifier.citation | [1] M. Blanchette, W. J. Kent, C. Riemer, L. Elnitski, A. F. Smit, K. M. Roskin,
R. Baertsch, K. Rosenbloom, H. Clawson, E. D. Green, D. Haussler, and W. Miller. Aligning multiple genomic sequences with the threaded blockset aligner. Genome Research, 14(4):708~715, April 2004. ISSN 1088-9051. doi: 10.1101/gr.1933104. URL http://dx.doi.org/10.1101/gr.1933104. [2] G. J. Chang and G. L. Nemhauser. The k-domination and k- stability problems on sun-free chordal graphs. SIAM Journal on Algebraic and Discrete Methods, 5(3):332~345, 1984. URL http: //scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal &id=SJMAEL000005000003000332000001&idtype=cvips&gifs=yes. [3] K. Chao and L. Zhang. Sequence Comparison: Theory and Meth- ods (Computational Biology). Springer, first edition, November 2008. ISBN 1848003196. URL http://www.amazon.com/ Sequence-Comparison-Methods-Computational-Biology/dp/ 1848003196/ref=sr_1_2?ie=UTF8&s=books&qid=1217402655&sr=1-2. [4] N. Chen, R. Engelberg, C. Nguyen, P. Raghavendra, A. Rudra, and G. Singh. Improved approximation algorithms for the spanning star forest problem. Ap- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 44~58, 2007. doi: 10.1007/978-3-540-74208-1n 4. URL http://dx.doi.org/10.1007/978-3-540-74208-1_4. [5] M. Chleb k and J. Chleb kov a. Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science, 354(3):320~ 338, April 2006. doi: 10.1016/j.tcs.2005.11.029. URL http://dx.doi.org/ 10.1016/j.tcs.2005.11.029. [6] E. Cockayne, S. Goodman, and S. Hedetniemi. A linear algorithm for the domination number of a tree. Information Processing Letters, 4(2):41~44,November 1975. doi: 10.1016/0020-0190(75)90011-3. URL http://dx.doi. org/10.1016/0020-0190(75)90011-3. [7] A. K. Dewdney. Fast turing reductions between problems in NP. Technical report, Departmet of Computer Science, The University of Western Ontario, 1981. [8] L. Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 8:128~140, 1741. URL http://www. math.dartmouth.edu/~euler/pages/E053.html. [9] U. Feige. A threshold of ln n for approximating set cover. Journal of Associ- ation for Computing Machinery, 45(4):634~652, July 1998. ISSN 0004-5411. doi: 10.1145/285055.285059. URL http://portal.acm.org/citation.cfm? id=285055.285059. [10] M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296~ 317, April 1995. ISSN 0097-5397. doi: 10.1137/S0097539793242618. URL http://portal.acm.org/citation.cfm?id=207985.207993. [11] T. W. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Dom- ination in Graphs (Pure and Applied Mathematics (Marcel Dekker)). CRC, January 1998. ISBN 0824700333. URL http://www.amazon. com/Fundamentals-Domination-Graphs-Applied-Mathematics/dp/ 0824700333. [12] T. W. Haynes, S. Hedetniemi, and P. Slater. Domination in Graphs (Pure and Applied Mathematics). CRC, January 1998. ISBN 0824700341. URL http: //www.amazon.com/Domination-Graphs-Pure-Applied-Mathematics/dp/ 0824700341. [13] D. K onig. Theorie der endlichen und unendlichen Graphen. Akademische Verlagsges., Leipzig, 1936. [14] W. McCuaig and B. Shepherd. Domination in graphs with minimum degree two. Journal of Graph Theory, 13(6):749~762, 1989. doi: 10.1002/jgt. 3190130610. URL http://dx.doi.org/10.1002/jgt.3190130610. [15] S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journalof Molecular Biology, 48(3):443~453, March 1970. ISSN 0022-2836. URL http://view.ncbi.nlm.nih.gov/pubmed/5420325. [16] C. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller, and L. Zhang. Approximating the spanning star forest problem and its applications to genomic sequence alignment. In SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 645~654, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245. URL http://portal.acm.org/citation.cfm?id=1283383.1283453. [17] C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. In STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 229~234, New York, NY, USA, 1988. ACM Press. ISBN 0897912640. doi: 10.1145/62212.62233. URL http: //portal.acm.org/citation.cfm?id=62233. [18] B. A. Reed. Paths, stars and the number three. Combinatorics, Probabil- ity & Computing, 5:277~295, 1996. URL http://dblp.uni-trier.de/rec/ bibtex/journals/cpc/Reed96. [19] L. Wang and T. Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1(4):337~348, 1994. ISSN 1066-5277. URL http://view.ncbi.nlm.nih.gov/pubmed/8790475. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40158 | - |
| dc.description.abstract | 我們在本篇論文中主要探討星狀生成樹林問題，以及其在二元圖上的相關結果。星狀生成樹林與控制集的關係不但易於了解，並且能夠快速轉換。雖然要找到這兩個問題的最佳解皆屬 NP-Hard, 但我們希望能夠憑藉著圖論學家在控制集上的豐碩成果，對星狀生成樹林做出進一步的探索。由於圖論學家多半探討的是控制集的大小，因此我們希望能藉由在計算複雜度與演算法效率上的分析對這個問題做出貢獻。
近來在生物資訊領域中，演化樹建構成為重要的探討主題。由於兩兩序列比對問題相較多重序列比對問題更易找出最佳解，某些軟體期望能藉由合併物種間兩兩比對的結果快速建出所有物種的演化樹。然而在序列重複區域極多的情形下，這些軟體往往會耗費很多空間，在最糟的狀況下甚至是以物種數的指數倍速度成長。為了解決這個問題， 2007 年 Nguyen et al. 提出了一套方法；倘若我們在建構演化樹過程中能以此方法建模，將比對結果轉化成二元圖，那麼該圖上夠大的星狀生成樹林能協助我們僅以線性的空間便找到理想的演化樹雛型。這使得二元樹上星狀生成樹林的問題再度吸引眾人的目光。 本篇論文中，我們首先證明星狀生成樹林在二元圖上的最佳化問題不但是 NP-Hard, 而且除非 NP = P, 否則此問題將有逼近比例的上限。接著，我們給出了一個在多項式時間內，對多數二元圖皆可找到 0.67 逼近比例生成樹林的演算法。 | zh_TW |
| dc.description.abstract | We study the spanning star forest problem (SSF) and its variation on bipartite graphs (BSSF). The relation between SSF and the dominating set problem (DOM), which has fruitful results in the literature, has been observed. The related optimization problems MSSF and MBSSF are of NP-Hard in general, and we hope to contribute to the issues by concentrating on theoretical aspects of approximation algorithms and combinatorial optimization.
In this thesis we demonstrate a general framework for approximating MBSSF based on available results of the dominating set problem. We hope to solve this problem by the upper bounds of the domination number. Based on several available domination numbers with constraints, we devise a polynomial time algorithm which obtains a 0.67 approximation ratio for most instances. We also construct some combinatorial witness of such a dominating set efficiently. By extending the dominating set to corresponding spanning star forest, we claim to have efficient algorithms for MBSSF. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-14T16:41:57Z (GMT). No. of bitstreams: 1 ntu-97-R95922101-1.pdf: 798469 bytes, checksum: d55e8ba149d1e46cbc5cd7f908889f51 (MD5) Previous issue date: 2008 | en |
| dc.description.tableofcontents | Abstract ii
Abstract in Chinese iii List of Figures vi List of Tables vii 1 Introduction 1 1.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Graph as Abstract Models . . . . . . . . . . . . . . . . . . . 2 1.1.2 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 Problem Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Overview of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Bipartite Graphs and Constructions of Phylogenetic Trees 9 2.1 Sequence Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Multiple Sequence Alignment . . . . . . . . . . . . . . . . . . . . . 12 2.3 Phylogenetic Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 TBA: Threaded Block Aligner . . . . . . . . . . . . . . . . . . . . . 13 2.5 Space-Saving Strategies by Bipartite Graphs . . . . . . . . . . . . . 14 3 Domination on Bipartite Graphs 15 3.1 Results of Approximability . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 A General Framework for Approximation . . . . . . . . . . . . . . . 19 3.3 Constructing Large Spanning Star Forests on Bipartite Graphs . . . 21 3.3.1 A Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.2 Union of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.3 More Complex Graphs . . . . . . . . . . . . . . . . . . . . . 22 3.3.4 A Working Example . . . . . . . . . . . . . . . . . . . . . . 28 4 Concluding Remarks 30 4.1 Recapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A McCuaig and Sheperd's Construction of Small Dominating Sets 33 Bibliography 38 | |
| dc.language.iso | en | |
| dc.title | 二元圖上星狀生成樹林之研究 | zh_TW |
| dc.title | A Study of the Spanning Star Forest Problem on Bipartite
Graphs | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 96-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 徐熊健(Shyu, Shyong-Jian),吳邦一(Bang Ye Wu) | |
| dc.subject.keyword | 組合最佳化,近似演算法,二元圖,星狀生成樹林,控制集, | zh_TW |
| dc.subject.keyword | combinatorial optimization,approximation algorithms,bipartite graph,spanning star forest,dominating set, | en |
| dc.relation.page | 40 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2008-08-01 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-97-1.pdf 目前未授權公開取用 | 779.75 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。