2分決定グラフ、ガウスの消去法、グラフ理論

概要

論文の詳細を見る
2分決定グラフは,論理関数を効率よく表現することができ,広く用いられている.本論文では,グラフや計算幾何の問題の解を特性関数を用いて論理関数で表してその論理関数を2分決定グラフで表現するとき,その2分決定グラフの大きさを小さくする問題が,グラフ理論で確立されているグラフとガウスの消去法の関連を用いることにより,高速かつ高性能で解けることを示す.2分決定グラフで表現するグラフの性質としては,全域木,マッチング,クリーク,安定集合を考え,その2分決定グラフをよい変数順序を選んで最小化するために,平面分離定理などのグラフ理論の成果を適用する.これにより,たとえば,任意のn点単純平面グラフに対して,その全域木を表す0(n)変数の論理関数は0(4^<<√<n>>>)の大きさの2分決定木で表現することができ,その安定集合を表すn変数の論理関数を0(n2^<<√<n>>>)の大きさの2分決定木で表現することができることを示す.また,OBDDパッケージを用いてこれらの論理関数を構成した計算機実験の結果についても述べる.本論文で扱う論理関数はグラフに関連したもので特殊なクラスではあるが,一般の論理関数を表す2分決定グラフに関しても有用な知見が得られる.
一般社団法人情報処理学会の論文
1994-09-21

2分決定グラフ、ガウスの消去法、グラフ理論

スポンサーリンク

概要

著者

関連論文

スポンサーリンク