On topological via minimization and routing
Moinul Hossain, Naveed A. Sherwani · 2002
The authors consider the topological via minimization problem in a bounded region. The problem is known to be NP-complete. An approximation algorithm is proposed for this problem, which solves the two-layer topological via minimization problem in a bounded region with at most 0.25m* more vias than the optimal number of vias, where m* is the size of the maximum two-planar subset of nets for the given problem. A graph-theoretic heuristic algorithm is also proposed to obtain a geometric routing from a topological solution.>