Finding a Length-Constrained Maximum-Density Path in a Tree |
| |
| Authors: | Rung-Ren?Lin Wen-Hsiung?Kuo Email author" target="_blank">Kun-Mao?ChaoEmail author |
| |
| Institution: | (1) Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan;(2) Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan;(3) Department of Computer Science and Information Engineering, Institute of Networking and Multimedia, National Taiwan University, Taipei, Taiwan |
| |
| Abstract: | 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 e1, e2,..., ek, is defined as  ki = 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. |
| |
| Keywords: | algorithm computational biology network design tree |
| 本文献已被 SpringerLink 等数据库收录！ |
|
