Finding a Length-Constrained Maximum-Density Path in a Tree

Authors: Lin, Rung-Ren¹; Kuo, Wen-Hsiung²; Chao, Kun-Mao³

Source: Journal of Combinatorial Optimization, Volume 9, Number 2, March 2005 , pp. 147-156(10)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

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 isin

E. The density of a path, say E₁, E₂,..., E_k, is defined as sum

^k_{i = 1} 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

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

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10878-005-6853-7

Affiliations: 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, Email: kmchao@csie.ntu.edu.tw

Publication date: 2005-03-01