A heuristic algorithm to solve constrained via minimization for three-layer routing problems
Kazunori Takahashi, Takahiro Watanabe · 2002
The constrained via minimization problem is the problem of minimizing the number of vias by changing the layer assignment of nets whose routing are given. It is already known that the problem is NP-complete even for three layer routing. The subject of the paper is to propose a heuristic algorithm VMBF, based an the breadth-first search, to solve the constrained via minimization for the three layer routing problem. Experimental results are provided to show the capability of the proposed algorithm.