進階搜尋


 
系統識別號 U0026-0812200911264376
論文名稱(中文) 在樹圖中求解限重最大密度子樹問題及其相關問題
論文名稱(英文) The Weight-Constrained Maximum-Density Subtree Problem and Related Problems on Trees
校院名稱 成功大學
系所名稱(中) 資訊工程學系碩博士班
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 93
學期 2
出版年 94
研究生(中文) 周庭宇
研究生(英文) Ting-Yu Chou
學號 p7692134
學位類別 碩士
語文別 英文
論文頁數 17頁
口試委員 指導教授-謝孫源
口試委員-簡仁宗
口試委員-張燕光
口試委員-朱治平
口試委員-李同益
中文關鍵字 演算法  動態規劃  樹圖  限重最大密度子樹 
英文關鍵字 dynamic programming  algorithms  trees  weight-constrained maximum-density subtree 
學科別分類
中文摘要 對一棵有 n 個點且每個點 v 皆伴隨著一 value-weight pair (val_v,w_v) 的樹T = (V,E),val_v 為一實數,w_v 為一非負的整數,此樹之密度定義為 Σ_v⊆V val_v / Σ_v∈V w_v。在樹 T 裡的一棵子樹為一連通子圖 (V′,E′) 且V′⊆ V 及E′⊆ E。給予兩整數 w_min 及 w_max,則在樹 T 上之限重最大密度子樹問題為在樹 T 裡尋找一子樹 T′= (V′,E′) 密度為最大且滿足 w_min ≦ Σ_v∈V′w_v ≦ w_max。本論文中,我們首先展示一O(w_maxn)-time 演算法在樹中尋找一限重最大密度路徑, 接著展示一O(w_max^2n)-time 演算法在樹中尋找一限重最大密度子樹。最後,給予一個真子集 S ⊂ V,我們展示一O(w_max^2n)-time 演算法在樹中尋找一包含所有在 S 裡的點之限重最大密度子樹。

英文摘要 Given a tree T = (V,E) of n vertices such that each node v is associated with a value-weight pair (val_v,w_v), where value val_v is a real number and weight w_v is a non-negative integer, the density of T is defined as Σ_v∈V val_v / Σ_v∈V w_v. A subtree of T is a connected subgraph (V′,E′) of T, where V′⊆ V and E′⊆ E. Given two integers w_min and w_max, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′= (V′,E′) satisfying w_min ≦ Σ_v∈V′w_v ≦ w_max. In this paper, we first present an O(w_maxn)-time algorithm to find a weight-constrained maximum-density path in a tree, and then present an O(w_max^2n)-time algorithm to find a weight-constrained maximum-density subtree in a tree. Finally, given a node subset S ⊂ V, we also present an O(w_max^2n)-time algorithm to find a weight-constrained maximum-density subtree of T which covers all the nodes in S.
論文目次 Contents i
List of Figures ii
1 Introduction 1
2 Preliminaries 3
3 Finding a weight-constrained maximum-density path 4
4 Finding a weight-constrained maximum-density subtree 8
4.1 The decision version is NP-complete . . . . . . 8
4.2 A polynomial-time algorithm for finding a weight-
constrained maximum-density subtree . . . . . 10
5 Finding a weight-constrained maximum-density Steiner tree 13
6 Concluding Remarks 16
Bibliography 17
參考文獻 [1] K. M. Chung and H. I. Lu, ``An optimal algorithm for the maximum-density segment problem," SIAM Journal on Computing, 34(2):373-387, 2004.

[2] M. H. Goldwasser, M. Y. Kao, and H. I. Lu, ``Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics," Proceedings of the Second International Workshop of Algorithms in Bioinformatics, Lecture Notes in Computer Science 2452, pp. 157-171, Rome, Italy, 2002, Springer-Verlag.

[3] X. Huang, ``An algorithm for identifying regions of a DNA sequence that satisfy a content requirement," Computer Applications in the Biosciences, 10(3):219-225, 1994.

[4] R. B. Inman, ``A denaturation map of the 1 phage DNA molecule determined by electron microscopy," Journal of Molecular Biology, 18:464-476, 1966.

[5] S. K. Kim, ``Linear-time algorithm for finding a maximum-density segment of a sequence," Information Processing Letters, 86(6):339-342, 2003.

[6] Y. L. Lin, X. Huang, T. Jiang, and K. M. Chao, ``MAVG: locating non-overlapping maximum average segments in a given sequence," Bioinformatics, 19(1):151-152, 2003.

[7] Y. L. Lin, T. Jiang, and K. M. Chao, ``Algorithms for locating the length-constrained heaviest segments, with aplications to biomolecular sequences analysis," Journal of Computer and System Sciences, 65(3):570-586, 2002.

[8] R. R. Lin, W. H. Kuo, and K. M. Chao, ``Finding a length-constrained maximum-density path in a tree," Journal of Combinatorial Optimization, 9(2):147-156, 2005.

[9] G. Macaya, J. P. Thiery, and G. Bernardi, ``An approach to the organization of eukaryotic genomes at a macromolecular level," Journal of Molecular Biology, 108:237-254, 1976.

[10] A. Nekrutenko and W. H. Li, ``Assesment of compositional heterogeneity within and between eukaryotic genomes," Genome Research, 10:1986-1995, 2000.

[11] P. Rice, I. Longden, and A. Bleasby, ``EMBOSS: The European molecular biology open software suite," Trends in Genetics, 16(6):276-277, 2000.

[12] M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston, MA 02116, 1997.

[13] N. Stojanovic, L. Florea, C. Riemer, D. Gumucio, J. Slightom, M. Goodman, W. Miller, and R. Hardison, ``Comparison of five methods for finding conserved sequences in multiple alignments of gene regulatory regions," Nucleic Acids Research, 27:3899-3910, 1999.

[14] D. B. West, Introduction to Graph Theory, 2nd ed, Prentice Hall, Upper Saddle River, NJ, 2001.

[15] B. Y. Wu, K. M. Chao, and C. Y. Tang, ``An efficient algorithm for the length-constrained heaviest path problem on a tree," Information Processing Letters, 69:63-67, 1999.

論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2008-06-14起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2008-06-14起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw