Efficient algorithms for multiple destinations routing

The multiple destinations routing (MDR) problem is formulated as a zero-one integer programming problem, and a technique for reducing the computation required for optimum solution is proposed. Three heuristics are designed for connecting a large number of nodes in the network. Heuristic A can offer different degrees of optimality with different amounts of time allowed for the solution of the MDR problem. Heuristic B is a modification of Prim´s algorithm for minimum spanning trees. It gives a fairly good solution with very little computation. Heuristic C is for minimizing the number of edges in the multicast tree. The MDR problem is identical to this problem when all link costs are the same. It always gives a better solution than Heuristic B. Simulation on two example networks shows that all three heuristics give better solutions (or lower-cost connection paths) than the improved RS algorithm