On minimal cost-reliability ratio spanning trees and related problems

doi:10.1016/0167-6377(96)00014-4

Full metadata record

DC Field	Value	Language
dc.contributor.author	Chang, YC	en_US
dc.contributor.author	Hsu, LH	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.identifier.issn	0167-6377	en_US
dc.identifier.uri	http://dx.doi.org/10.1016/0167-6377(96)00014-4	en_US
dc.identifier.uri	http://hdl.handle.net/11536/1152	-
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.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
dc.identifier.doi	10.1016/0167-6377(96)00014-4	en_US
dc.identifier.journal	OPERATIONS RESEARCH LETTERS	en_US
dc.citation.volume	19	en_US
dc.citation.issue	2	en_US
dc.citation.spage	65	en_US
dc.citation.epage	69	en_US
dc.contributor.department	資訊工程學系	zh_TW
dc.contributor.department	Department of Computer Science	en_US
Appears in Collections:	Articles

Files in This Item:

A1996VF92200003.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.