Routing in VLSI Design and Communication Networks
Global routing in VLSI design and multicast routing in communication networks:
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 multicommodity flow problem in lattice graphs, where the total cost is the sum of edge costs and the bend-dependent vertex costs.
• integer linear programming formulation;
• approximation algorithms for min-max resource-sharing problems;
• block problems and virtual layer method;
• results and more applications;
• future work.
• 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
