Finding a maximum-density path in a tree under the weight and length constraints

Sun-Yuan Hsieh, Chih Sheng Cheng

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

Let T = (V, E) be a tree with n nodes such that each node v is associated with a value-weight pair(valv, wv), where the valuevalv is a real number and the weightwv is a positive integer. The density of a path P = 〈 v1, v2, ..., vk 〉 is defined as ∑i = 1k vali / ∑i = 1k wi. The weight of P, denoted by w (P), is ∑i = 1k wi. Given a tree of n nodes, two integers wmin and wmax, and a length lower bound L, we present a pseudo-polynomial O (wmax n L)-time algorithm to find a maximum-density path P in T such that wmin ≤ w (P) ≤ wmax and the length of P is at least L.

Original languageEnglish
Pages (from-to)202-205
Number of pages4
JournalInformation Processing Letters
Volume105
Issue number5
DOIs
Publication statusPublished - 2008 Feb 29

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Finding a maximum-density path in a tree under the weight and length constraints'. Together they form a unique fingerprint.

Cite this