Article ID: | iaor200947168 |
Country: | Netherlands |
Volume: | 43 |
Issue: | 1 |
Start Page Number: | 83 |
End Page Number: | 95 |
Publication Date: | Jan 2009 |
Journal: | Journal of Global Optimization |
Authors: | Wang Qin, Liu Longcheng |
Keywords: | minimum spanning trees |
In this paper, we consider the constrained inverse min–max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck–type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times.