Hfs. Chen et Dt. Lee, ON CROSSING MINIMIZATION PROBLEM, IEEE transactions on computer-aided design of integrated circuits and systems, 17(5), 1998, pp. 406-418
In this paper, we consider a problem related to global routing postopt
imization: the crossing minimization problem (CMP), Given a global rou
ting representation, the CMP is to minimize redundant crossings betwee
n every pair of nets. In particular, there are two kinds of CMP: const
rained CMP (CCMP) and unconstrained CMP (UCMP). These problems have be
en studied previously in [11] where an O(m(2)n)i algorithm was propose
d for CCMP, and in [15] where an (mn(2) + xi(2)) algorithm was propose
d for UCMP where m is the total number of modules, n is the number of
nets, and xi is the number of crossings defined by an initial global r
outing topology, We present a simpler and faster O(mn) algorithm for C
CMP and an O[n(m + xi)] time algorithm for UCMP, Both algorithms impro
ve over the time bounds of the previously proposed algorithms. The nov
el part of our algorithm is that it uses the plane embedding informati
on of globally routed nets in the routing area to construct a graph-ba
sed framework and obtain a good junction terminal assignment that mini
mizes the number of crossings.