On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI de-sign and the multicast routing problem in communication networks. We first propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of over-all wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming formulation of both problems and solve the linear programming (LP) relaxations by the fast approx