On the complexity of the robust spanning tree problem with interval data

On the complexity of the robust spanning tree problem with interval data

0.00 Avg rating0 Votes
Article ID: iaor20043257
Country: Netherlands
Volume: 32
Issue: 1
Start Page Number: 36
End Page Number: 40
Publication Date: Jan 2004
Journal: Operations Research Letters
Authors: ,
Keywords: combinatorial analysis
Abstract:

This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It shows that the problem is NP-complete, settling the conjecture of Kouvelis and Yu, and that it remains so for complete graphs or when the intervals are all [0,1]. These results indicate that the difficulty of RSTID stems from both the graph topology and the structure of the cost intervals, suggesting new directions for search algorithms.

Reviews

Required fields are marked *. Your email address will not be published.