A polynomial solvable minimum risk spanning tree problem with interval data

Xujin Chen, Jie Hu and Xiaodong Hu

European Journal of Operational Research, 2009, vol. 198, issue 1, 43-46

Abstract: We propose and study a new model for the spanning tree problem with interval data, the Minimum Risk Spanning Tree (MRST) problem, that finds diverse applications in network design. Given an underlying network G=(V,E), each link e[set membership, variant]E can be established by paying a cost , and accordingly takes a risk of link failure. The MRST problem is to establish a spanning tree T in G of total cost not more than a given constant so that the risk sum over the links in T is minimized. We prove that the MRST problem can be solved in polynomial time, and thus has algorithmic aspect more satisfactory than the NP-hard robust spanning tree problem with interval data.

Keywords: Combinatorial; optimization; Spanning; tree; Interval; data (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00501-8
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:198:y:2009:i:1:p:43-46

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().