對一棵有 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.

[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.