近年のLSIの高密度化に伴う発熱の問題、携帯機器の普及などから LSIの低消費電力、小面積化設計の必要性が高まってきている。 この要求に対して従来のCMOS回路に比べ、低消費電力、小面積のパストラン ジスタ論理が注目されている。パストランジスタ論理の設計手法として、論理関 数を表現する二分決定グラフ(Binary Decision Diagram、BDD)のグラフ構造 をトランジスタ回路に置き換えて直接構成する手法がある。 BDDの中でもFree BDD(FBDD)は少ない節点数で関数を表現できることが知られ ているため、その最小化についての研究が行われている。 これまでに提案されているFBDDの最小化アルゴリズムは変数ラベル 付けにおける探索順序に着目すると、幅優先探索と深さ優先探索の 二つに分けられる。 パストランジスタ論理では5個から10個程度の入力変数を扱うことが 望まれるが、幅優先探索は計算に使用するメモリ量、深さ優先探索では計算にかかる 時間が問題となり、どちらも実用的には5変数までの最小化しか行えていない。 本論文では、実時間内で6変数以上の最小化を可能にするべく 幅優先探索と深さ優先探索を組み合わせたアルゴリズムについて考察する。