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

Authors: Lin, Rung-Ren1; Kuo, Wen-Hsiung2; Chao, Kun-Mao3

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

Publisher: Springer

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content

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 E1, E2,..., Ek, is defined as sumki = 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 1le L le 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: 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

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$47.00 plus tax      Refund Policy

 

OR

Back to top

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages.
Page Help Click here for Page Help
Shopping cart
Tools
Sign in






Need to register?
Sign up here
Text size: A | A | A | A