Abstract
隨著電子技術的進步，更多更細小的電晶體可以放入積體電路之內，使得超大型積體電路更形複雜，電腦輔助超大型積體電路設計也越來越重要。為了平衡設計時間以及電路面積，許多種技術被研究了，其中一個相當成功的例子，叫做可程式化邏輯陣列。而可程式化邏輯具有分散的選用，大量的浪費了電路面積，許多減少電路面積的技術被研究了。其中之一便是摺疊技巧。一個廣用的摺疊技巧是指拔出一最大數目的摺疊對，，而不違反摺疊規則，此一技巧可具有多重的切點。而二分摺疊則是只准許切點唯一的一種摺疊技巧。我們先將可程式化邏輯陣列換成可摺疊性圖則形，此一圖形的節點（node）代表可程式化邏輯陣列的行，而邊（edge）代表此二行可以摺疊。而此一問題便轉換成為在可摺疊性圖形上找一最大二分子圖。我們設計了一個分支和界定（branch-and-bound）演算法去尋找最佳解，我們的分支方法是基於互斥觀念上，我們在尋找樹（tree）的每一個樹節點上，選出一個摺疊對（folding pair），而在此一節點上，對應此一摺疊對的互斥對，便構成此一樹節點的所有分支。而選擇第一個摺疊對的方法是選出與別的摺疊對之間具有最小不相容性的摺疊對。我們的上界求法及消除不必要的分支均以定理或補助定理的方式出現。求上界的方法，有下面三種：（一）所有可摺疊行的個數除以二。（二）在圖形中由節點的個數關係。（三）未摺疊行之型態（type）導出。接著三個消除不必要找尋的技術再消除不必要的分支，第一個是找出互斥集合使分支樹變小。而第二個技術是找出與現分支具有一些包含關係的分支，把它們去除。而第三個技術為把一些與目前解有關而可以消除的分支去除。