Grade of service Euclidean Steiner minimum trees
Guoliang Xue, Guo-Hui Lin, Ding‐Zhu Du · 2003
In this paper, we study the grade of service Steiner tree (GOSST) problem-a generalization of the Euclidean Steiner minimum tree problem. We present efficient approximation algorithms for the special cases where there are only two or three grades of service requests. We also present an exact algorithm and a powerful 5-optimal heuristic algorithm for the general case, together with computational results.