Department of Computer Science and Information Engineering, National Taiwan University; Department of Electrical Engineering, National Taiwan University; Department of Computer Science and Information Engineering, Institute of Networking and Multimedia, National Taiwan University.Lin, Rung-RenRung-RenLinKuo, Wen-HsiungWen-HsiungKuoKUN-MAO CHAO2006-09-272018-07-052006-09-272018-07-05200513826905http://ntur.lib.ntu.edu.tw//handle/246246/20060927122859226973https://www.scopus.com/inward/record.uri?eid=2-s2.0-24144489027&doi=10.1007%2fs10878-005-6853-7&partnerID=40&md5=05a96e08c4ef8813172795244fdaf90eLet T =(V E w )be anundirected and weighted tree with node set V and edge set E, where w (e) is an edge weight function for e ∈E. The density of a path, say e1 e2 ...,ek ,isdefined as k i =1 w (ei )/k. The length of a path is the number of its edges. Given a tree with n edges and a lower bound L where 1 ≤L ≤n, this paper presents two efficient algorithms for finding a maximum-density path of length at least L in O(nL) time. One of them is further modified to solve some special cases such as full m-ary trees in O(n) time.Let T = (V,E,w) be an undirected and weighted tree with node set V and edge set E, where w(e) is an edge weight function for e ∈ E. The density of a path, say e 1, e 2,..., e k , is defined as Σ i = 1k w(e i )/k. The length of a path is the number of its edges. Given a tree with n edges and a lower bound L where 1 ≤ L ≤ n, this paper presents two efficient algorithms for finding a maximum-density path of length at least L in O(nL) time. One of them is further modified to solve some special cases such as full m-ary trees in O(n) time. © 2005 Springer Science + Business Media, Inc.application/pdf155676 bytesapplication/pdfzh-TWalgorithmcomputational biologynetwork designtreejournal article10.1007/s10878-005-6853-72-s2.0-24144489027http://ntur.lib.ntu.edu.tw/bitstream/246246/20060927122859226973/1/2005_treepath_jco.pdf