On minimal cost-reliability ratio spanning trees and related problems
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
69 | en_US |
dc.citation.spage |
65 | en_US |
dc.citation.volume |
19 | en_US |
dc.citation.woscount |
1 | en_US |
dc.contributor.author |
Chang, YC | en_US |
dc.contributor.author |
Hsu, LH | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
資訊科學與工程研究所 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.contributor.department |
Institute of Computer Science and Engineering | en_US |
dc.date.accessioned |
2019-04-02T05:58:33Z | |
dc.date.available |
2019-04-02T05:58:33Z | |
dc.date.issued |
1996-08-01 | en_US |
dc.description.abstract |
The minimal cost-reliability ratio spanning tree problem is to find a spanning tree such that the cost-reliability ratio is minimized. This problem can also be treated as a specific version of a more generalized problem discussed by Hassin and Tamir. By Hassin and Tamir's approach, the minimal cost-reliability ratio spanning tree problem can be solved in O(q(4)) where q is the number of edges in the graph. In this paper, we reduce the complexity of the algorithm proposed by Hassin and Tamir to O(q(3)). Furthermore using our approach, related algorithms proposed by Hassin and Tamir can also be improved by a factor of O(q). | en_US |
dc.identifier.doi |
10.1016/0167-6377(96)00014-4 | en_US |
dc.identifier.issn |
0167-6377 | en_US |
dc.identifier.journal |
OPERATIONS RESEARCH LETTERS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/0167-6377(96)00014-4 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/149298 | |
dc.identifier.wosnumber |
WOS:A1996VF92200003 | en_US |
dc.language.iso |
en_US | en_US |
dc.subject |
combinatorial algorithms | en_US |
dc.subject |
complexity | en_US |
dc.subject |
spanning trees | en_US |
dc.title |
On minimal cost-reliability ratio spanning trees and related problems | en_US |
dc.type |
Article | en_US |
檔案
本條目沒有附加檔案。
所屬典藏: 期刊論文