University of Winnipeg
Constrained MinimumSteiner Tree (CMST) problem is a key issue in multicast routing with Quality of Service (QoS) support. Many heuristics have been developed to solve this NP-complete problem. In recent years, some interesting work has been done to use the Greedy Randomized Adaptive Search Procedure (GRASP) to solve this problem. While it helps to achieve very high success ratios of finding optimal solutions on networks of small or medium sizes (less than 100 nodes), a high computation time is also required, usually in the range of tens of seconds.