The weight-constrained maximum-density subtree problem and related problems in trees

Sun Yuan Hsieh, Ting Yu Chou

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)

摘要

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val v,w v ), where value val v is a real number and weight w v is a non-negative integer, the density of T is defined as Σv∈V Valu/Σv∈Vwv. A subtree of T is a connected subgraph (V′,E′) of T, where V′V and E′E. Given two integers w min∈ and w max, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w minΣv V′ w v ≤w max. In this paper, we first present an O(w max n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w max 2 n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S⊂V, we also present an O(w max 2 n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.

原文English
頁(從 - 到)366-380
頁數15
期刊Journal of Supercomputing
54
發行號3
DOIs
出版狀態Published - 2010 十二月

All Science Journal Classification (ASJC) codes

  • 軟體
  • 理論電腦科學
  • 資訊系統
  • 硬體和架構

指紋

深入研究「The weight-constrained maximum-density subtree problem and related problems in trees」主題。共同形成了獨特的指紋。

引用此