**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.

• 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**