An improved algorithm for finding a length-constrained maximum-density subtree in a tree
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
164 | en_US |
dc.citation.issue |
2 | en_US |
dc.citation.spage |
161 | en_US |
dc.citation.volume |
109 | en_US |
dc.citation.woscount |
3 | |
dc.contributor.author |
Su, Hsin-Hao | en_US |
dc.contributor.author |
Lu, Chin Lung | en_US |
dc.contributor.author |
Tang, Chuan Yi | en_US |
dc.contributor.department |
生物科技學系 | zh_TW |
dc.contributor.department |
生物資訊及系統生物研究所 | zh_TW |
dc.contributor.department |
Department of Biological Science and Technology | en_US |
dc.contributor.department |
Institude of Bioinformatics and Systems Biology | en_US |
dc.date.accessioned |
2014-12-08T15:10:29Z | |
dc.date.available |
2014-12-08T15:10:29Z | |
dc.date.issued |
2008-12-31 | en_US |
dc.description.abstract |
Given a tree T with weight and length on each edge, as well as a lower bound L and an upper bound U, the so-called length-constrained maximum-density subtree problem is to find a maximum-density subtree in T such that the length of this subtree is between L and U. In this study, we present an algorithm that runs in O (nU log n) time for the case when the edge lengths are positive integers, where n is the number of nodes in T, which is an improvement over the previous algorithms when U = Omega(log n). In addition, we show that the time complexity Of Our algorithm can be reduced to (nL log n/L), when the edge lengths being considered are uniform. (C) 2008 Elsevier B.V. All rights reserved. | en_US |
dc.identifier.doi |
10.1016/j.ipl.2008.09.027 | en_US |
dc.identifier.issn |
0020-0190 | en_US |
dc.identifier.journal |
INFORMATION PROCESSING LETTERS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.ipl.2008.09.027 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/8011 | |
dc.identifier.wosnumber |
WOS:000261792700016 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Algorithms | en_US |
dc.subject |
Dynamic programming | en_US |
dc.subject |
Trees | en_US |
dc.subject |
Network design | en_US |
dc.subject |
Divide and conquer | en_US |
dc.title |
An improved algorithm for finding a length-constrained maximum-density subtree in a tree | en_US |
dc.type |
Article | en_US |
檔案
- 000261792700016.pdf (140.4 KB, Adobe PDF)
所屬典藏: 期刊論文