Title :
Grade of service Euclidean Steiner minimum trees
Author :
Xue, Guoliang ; Lin, Guo-Hui ; Du, Ding-Zhu
Author_Institution :
Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USA
Abstract :
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
Keywords :
approximation theory; telecommunication network routing; trees (mathematics); 5-optimal heuristic algorithm; Euclidean Steiner minimum trees; approximation algorithms; computational results; grade of service Steiner tree problem; service requests; Approximation algorithms; Computer science; Cost function; Educational institutions; Heuristic algorithms; Internet; Joining processes; Partitioning algorithms; Polynomials; Steiner trees;
Conference_Titel :
Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-5471-0
DOI :
10.1109/ISCAS.1999.780125
