Optimal joining of compacted cells

Three algorithms to join two compacted cells by using a combination of stretching and river routing are developed. Each of these obtains the minimum area joining. One algorithm obtains a minimum area joining that also minimizes the length of the longest wire. Another obtains a minimum area joining that has the least possible total wire length. The simplest of the algorithms guarantees only a minimum are joining. All algorithms have a low-order polynomial complexity. Experimental results indicate that the algorithms obtain joinings that are significantly superior to those obtained using the heuristic of G. Cheng and A. Despain (1989)