We develop two fast algorithms for the layering problem that arises when the single row routing approach to wire layout is used. Both these algorithms are for the case when the upper and lower street capacities are two. While neither of these algorithms guarantees to produce an optimal layering, both are empirically determined to produce better layerings than an earlier proposed algorithm for this problem. In addition, our algorithms run much faster than the earlier algorithm.
展开▼