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

Sun-Yuan Hsieh, Chih Sheng Cheng

研究成果: Article同行評審

8 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)202-205
頁數4
期刊Information Processing Letters
105
發行號5
DOIs
出版狀態Published - 2008 二月 29

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 訊號處理
  • 資訊系統
  • 電腦科學應用

指紋

深入研究「Finding a maximum-density path in a tree under the weight and length constraints」主題。共同形成了獨特的指紋。

引用此