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

Amoia, 1971, Invariance properties of central trees, IEEE Trans. Circuit Theory, CT-18, 465, 10.1109/TCT.1971.1083314 I. Aron, P. Van Hentenryck, A constraint satisfaction approach to the robust spanning tree problem with interval data, in: Proceedings of the 18th Conference on UAI, Edmonton, Canada, August 1–4, 2002. D. Bertsimas, M. Sim, Robust discrete optimization, Working Paper, Operations Research Center, MIT, January 2002. S. Bezrukov, F. Kaderali, W. Poguntke, On central spanning trees of a graph, in: Lecture Notes in Computer Science, Vol. 1120, Springer, Berlin, 1996, pp. 53–58. Deo, 1966, A central tree, IEEE Trans. Circuit Theory, CT-13, 439, 10.1109/TCT.1966.1082617 Hakimi, 1961, On trees of a graph and their generation, J. Franklin Inst., 272, 347, 10.1016/0016-0032(61)90036-9 F. Kaderali, A counterexample to the algorithm of Amoia and Cottafava for finding central trees, Technical Report FB 19, TH Darmstadt, June 1973, Preprint. Kishi, 1969, Maximally distant trees and principal partition of a linear graph, IEEE Trans. Circuit Theory, CT-16, 323, 10.1109/TCT.1969.1082966 Kouvelis, 1997, 10.1007/978-1-4757-2620-6 Kozina, 1994, Interval spanning tree problem, Interval Comput., 1, 42 Y.Y. Lee, Use of compound matrices in topological analysis, Master's Thesis, Kansas State University, Manhatten, KS, 1968. Malik, 1968, On Deo's central tree concept, IEEE Trans. Circuit Theory, CT-15, 283, 10.1109/TCT.1968.1082806 N. Malik, Y.Y. Lee, Finding trees and signed tree pairs by the compound method, in Tenth Midwest Symposium on Circuit Theory, 1967, pp. VI-5-1-VI-5-11. Mayeda, 1965, Generation of trees without duplications, IEEE Trans. Circuit Theory, CT-12, 181, 10.1109/TCT.1965.1082432 R. Montemanni, L. Gambardella, A. Rizzoli, A. Donati, A branch and bound algorithm for the robust spanning tree problem with interval data, Technical Report No. IDSIA-10-02, Istituto Dalle Molle di Studi sull'Intelligenza Artificiale, 2002. S. Shinoda, T. Kawamoto, Central trees and critical sets, in: D.E. Kirk (Ed.), Proceedings of the 14th Asilomar Conference on Circuit, Systems and Computers, Vol. 108, Pacific Grove, California, 1980, pp. 183–187. S. Shinoda, T. Kawamoto, On central trees of a graph, in: Lecture Notes in Computer Science, Vol. 108, Springer, Berlin, 1981, pp. 137–151. S. Shinoda, K. Saishu, Conditions for an incidence set to be a central tree, Technical Report CAS80-6, Institute of Electrical and Communication Engineering, Japan, 1980. Thulasiraman, 1992 Yaman, 2001, The robust spanning tree problem with interval data, Oper. Res. Lett., 29, 31, 10.1016/S0167-6377(01)00078-5