The global routing problem is formulated as a multiterminal, multicommodity flow problem with integer flows, An E-optimal 2-terminal multicommodity flow algorithm with fractional flows is extended to handle multiterminal commodities, Our adaptation of this network flow algorithm seeks to maximize overall routability by minimizing edge congestion as opposed to conventional techniques which usually seek to minimize wire length. We show that under certain conditions, our approach derives an approximate optimal solution. We apply a randomized rounding procedure to derive an integer solution from the fractional multicommodity flow solution. Experimental results demonstrate that this network flow algorithm can be realistically used to route industrial sized circuits with reduced congestion.

The global routing problem is formulated as a multiterminal, multicommodity flow problem with integer flows.An epsilon bound 2-terminal multicommodity flow algorithm with fractional flows is adapted to handle multitermirtal commodities.We show that under certain conditions, our approach derives an approximate optimal solution.The experimental results with benchmark data are quite promising.