On minimal cost-reliability ratio spanning trees and related problems

檔案

日期

1996-08-01

類型

期刊名稱

OPERATIONS RESEARCH LETTERS

卷期與頁次

第 19 卷第 2 期,頁 65–69

ISSN

0167-6377

語言

英文

摘要

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).

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chang, Y., & Hsu, L. (1996). On minimal cost-reliability ratio spanning trees and related problems. OPERATIONS RESEARCH LETTERS, 19(2), 65–69. https://doi.org/10.1016/0167-6377(96)00014-4

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/1152