On minimal cost-reliability ratio spanning trees and related problems
| dc.citation.epage | 69 | en_US |
| dc.citation.issue | 2 | en_US |
| dc.citation.spage | 65 | en_US |
| dc.citation.volume | 19 | en_US |
| dc.contributor.author | Chang, YC | en_US |
| dc.contributor.author | Hsu, LH | en_US |
| dc.contributor.department | 資訊工程學系 | zh_TW |
| dc.contributor.department | Department of Computer Science | en_US |
| dc.date.accessioned | 2014-12-08T15:02:29Z | |
| dc.date.available | 2014-12-08T15:02:29Z | |
| 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/1152 | |
| 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 |