https://scholars.lib.ntu.edu.tw/handle/123456789/302479
標題: | Finding a length-constrained maximum-density path in a tree | 作者: | Lin, Rung-Ren Kuo, Wen-Hsiung KUN-MAO CHAO |
公開日期: | 2003 | 卷: | 2906 | 起(迄)頁: | 78 - 87 | 來源出版物: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 摘要: | Let T = (V,E,w) be a rooted, 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 e1,e2,...,ek, is defined as ∑i=1k w(ei)/k. Given a tree with n edges, 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. © Springer-Verlag Berlin Heidelberg 2003. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-35248816903&doi=10.1007%2f978-3-540-24587-2_10&partnerID=40&md5=19df72f9163a1a0f7fed38ee13a019d5 http://scholars.lib.ntu.edu.tw/handle/123456789/302479 |
ISSN: | 03029743 | DOI: | 10.1007/978-3-540-24587-2_10 |
顯示於: | 生醫電子與資訊學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。