Weight-constrained and density-constrained paths in a tree
Pages 126 - 134
Abstract
Let T be a tree of n nodes in which each edge is associated with a value and a weight that are a real number and a positive integer, respectively. Given two integers w m i n and w m a x, and two real numbers d m i n and d m a x, a path P in a tree is feasible if the sum of the edge weights in P is between w m i n and w m a x, and the ratio of the sum of the edge values in P to the sum of the edge weights in P is between d m i n and d m a x . In this paper, we first present an O ( n log 2 n + h ) -time algorithm to find all feasible paths in a tree, where h = O ( n 2 ) if the output of a path is given by its end-nodes. Then, we present an O ( n log 2 n ) -time algorithm to count the number of all feasible paths in a tree. Finally, we present an O ( n log 2 n + h ) -time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths.
References
[1]
R.M. Aliguliyev, Performance evaluation of density-based clustering methods, Inform. Sci., 179 (2009) 3583-3602.
[2]
M. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest, R.E. Tarjan, Time bounds for selection, J. Comput. System Sci., 7 (1973) 448-461.
[3]
G.S. Brodal, A.G. Jørgensen, A linear time algorithm for the k maximal sums problem, in: Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 4708 (2007) pp. 442-453.
[4]
J. Bukor, L. Misšík, J.T. Tóth, Dependence of densities on a parameter, Inform. Sci., 179 (2009) 2903-2911.
[5]
K.M. Chao, R.C. Hardison, W. Miller, Recent developments in linear-space alignment methods: a survey, J. Comput. Biol., 1 (1994) 271-291.
[6]
K.M. Chung, H.I. Lu, An optimal algorithm for the maximum-density segment problem, SIAM J. Comput., 34 (2004) 373-387.
[7]
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, MA, 2009.
[8]
G.N. Frederickson, An optimal algorithm for selection in a min-heap, Inform. and Comput., 104 (1993) 197-214.
[9]
A. Ghosh, A. Halder, M. Kothari, S. Ghosh, Aggregation pheromone density based data clustering, Inform. Sci., 178 (2008) 2816-2831.
[10]
A.J. Goldman, Optimal center location in simple networks, Transp. Sci., 5 (1971) 212-221.
[11]
M.H. Goldwasser, M.Y. Kao, H.I. Lu, Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics, J. Comput. System Sci., 70 (2005) 128-144.
[12]
S.Y. Hsieh, C.S. Cheng, Finding a maximum-density path in a tree under the weight and length constraints, Inform. Process. Lett., 105 (2008) 202-205.
[13]
S.Y. Hsieh, T.Y. Chou, Finding a weight-constrained maximum-density subtree in a tree, in: Proceedings of the 16th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol. 3827 (2005) pp. 944-953.
[14]
L.K. Hua, Applications of mathematical models to wheat harvesting, Chin. Math., 2 (1961) 77-91.
[15]
X. Huang, An algorithm for identifying regions of a DNA sequence that satisfy a content requirement, Comput. Appl. Biosci., 10 (1994) 219-225.
[16]
R.B. Inman, A denaturation map of the 1 phage DNA molecule determined by electron microscopy, J. Mol. Biol., 18 (1966) 464-476.
[17]
Z. Jiang, Y.X. Huang, Parametric calibration of speed-density relationships in mesoscopic traffic simulator with data mining, Inform. Sci., 179 (2009) 2002-2013.
[18]
S.K. Kim, Finding a longest nonnegative path in a constant degree tree, Inform. Process. Lett., 93 (2005) 275-279.
[19]
H.C. Lau, T.H. Ngo, B.N. Nguyen, Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics, Discrete Optim., 3 (2006) 385-391.
[20]
Y.L. Lin, T. Jiang, K.M. Chao, Algorithms for locating the length-constrained heaviest segments, with applications to biomolecular sequences analysis, J. Comput. System Sci., 65 (2002) 570-586.
[21]
R.R. Lin, W.H. Kuo, K.M. Chao, Finding a length-constrained maximum-density path in a tree, J. Combin. Optim., 9 (2005) 147-156.
[22]
T.C. Lin, D.T. Lee, Algorithmic studies of sequence manipulation and related problems, National Taiwan University, Taiwan, 2007.
[23]
G. Macaya, J.P. Thiery, G. Bernardi, An approach to the organization of eukaryotic genomes at a macromolecular level, J. Mol. Biol., 108 (1976) 237-254.
[24]
E.M. McCreight, Priority search trees, SIAM J. Comput., 14 (1985) 257-276.
[25]
A. Nekrutenko, W.H. Li, Assessment of compositional heterogeneity within and between eukaryotic genomes, Genome Res., 10 (2000) 1986-1995.
[26]
P. Rice, I. Longden, A. Bleasby, EMBOSS: The European molecular biology open software suite, Trends Genet., 16 (2000) 276-277.
[27]
D.D. Sleator, R.E. Tarjan, Self-adjusting heaps, SIAM J. Comput., 15 (1986) 52-69.
[28]
N. Stojanovic, L. Florea, C. Riemer, D. Gumucio, J. Slightom, M. Goodman, W. Miller, R. Hardison, Comparison of five methods for finding conserved sequences in multiple alignments of gene regulatory regions, Nucleic Acids Res., 27 (1999) 3899-3910.
[29]
H.H. Su, C.L. Lu, C.Y. Tang, An improved algorithm for finding a length-constrained maximum-density subtree in a tree, Inform. Process. Lett., 109 (2008) 161-164.
[30]
J.W.J. Williams, Algorithm 232: heapsort, Commun. ACM, 7 (1964) 347-348.
[31]
B.Y. Wu, K.M. Chao, C.Y. Tang, An efficient algorithm for the length-constrained heaviest path problem on a tree, Inform. Process. Lett., 69 (1999) 63-67.
- Weight-constrained and density-constrained paths in a tree
Recommendations
The weight-constrained maximum-density subtree problem and related problems in trees
Given a tree T =( V , E ) of n nodes 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 ...
An improved algorithm for finding a length-constrained maximum-density subtree in a tree
Given a tree T with weight and length on each edge, as well as a lower bound L and an upper bound U, the so-called length-constrained maximum-density subtree problem is to find a maximum-density subtree in T such that the length of this subtree is ...
Finding a maximum-density path in a tree under the weight and length constraints
Let T=(V,E) be a tree with n nodes such that each node v is associated with a value-weight pair(val"v,w"v), where the valueval"v is a real number and the weightw"v is a positive integer. The density of a path P= is defined as @__ __"i"="1^kval"i/@__ __"...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 10 January 2015
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in