Routing in VLSI Design and Communication Networks

Global routing in VLSI design and multicast routing in communication networks:
 

• integer linear programming formulation;
• approximation algorithms for min-max resource-sharing problems;
• block problems and virtual layer method;
• results and more applications;
• future work.

Theorem: There is a polynomial time algorithm for the shortest path problem in lattice graphs, where the total cost is the sum of edge costs and the bend-dependent vertex costs. 

 

Theorem: There is a polynomial time algorithm for the splitable min-cost flow problem in lattice graphs, where the total cost is the sum of edge costs and the bend-dependent vertex costs.

Theorem: There is a polynomial time algorithm for the splitable min-cost multicommodity flow problem in lattice graphs, where the total cost is the sum of edge costs and the bend-dependent vertex costs.

Download this paper at: http://www.mediafire.com/?4maquc4b8espx0q