Correction to "Boundary single-layer routing with movable terminals"
Kuo-Feng Liao, Majid Sarrafzadeh · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1994
In boundary single-layer routing with slidable or permutable terminals (BSLR-S or BSLR-P), the assumption that each net may have more than one terminal in a range or cluster should be removed. An example that shows Pick-Closest might report "unsolvable" for a solvable instance is considered. It is clear that the instance is solvable if (and only if) the two terminals of net N/sub 1/ are assigned to vertices c and d. However, Pick-Closest will assign the two terminals of net N/sub 1/ to vertices /spl lcub/b,c/spl rcub/ or /spl lcub/d,e/spl rcub/, then report "unsolvable" due to the failure in routing net N/sub 2/. Thus, Pick-Closest only works in instances when each net has at most one terminal in a range. Since BSLR-P also includes slidable terminals, we employ Pick-Closest to solve BSLR-P when TR-permutation is determined by Greedy-Assignment. Thus in BSLR-P, each net can have at most one terminal in a cluster as well. The time complexity of the problem of boundary single-layer routing with slidable and permutable terminals remains open if a net is allowed to have multiple terminals in a cluster.>