フロンティア法による強連結な部分グラフの列挙
Enumerating Strongly Connected Subgraphs
Using Frontier Based Search
鈴木 浩史
1∗石畠 正和
1湊 真一
1Hirofumi Suzuki
1Masakazu Ishihata
1Shin-ichi Minato
11
北海道大学 大学院情報科学研究科
1
Graduate School of Information Science and Technology, Hokkaido University
Abstract: Directed graphs in real world have the important property, strongly connected. There are a few major existing results for enumerating strongly connected subgraphs. Tarjan showed a method for enumerating strongly connected components in a give directed graph, and Boros etal. showed a method for enumerating minimal strongly connected subgraphs in a give strongly
connected graph. In particular, studies on enumerating all strongly connected subgraphs are not known. In this paper, we propose a method for enumerating all the strongly connected subgraphs in a given directed graph, which is a new frontier-based search. A frontier-based search constructs a data structure, zero-suppressed binary decision diagram (ZDD), indexing all the solutions com-pactly. On the computational experiments, our method constructs a ZDD indexing 6.5 × 1033 strongly connected subgraphs in a few minutes.
1
はじめに
有向グラフを特徴付ける重要な性質に強連結と呼ば れるものがある．本稿では，与えられた有向グラフか ら，強連結な性質を持つ部分グラフ (以下，強連結部分 グラフ) を効率良く列挙する手法を提案する．強連結部 分グラフの列挙は，ネットワークの信頼性評価，マルコ フ遷移過程が内包する部分構造の抽出，有限オートマ トンの最小化，フローチャートの解析などに関連があ る．強連結部分グラフの列挙に関する研究には，Tarjan による強連結成分の列挙 [9] および Boros らによる極小 な強連結部分グラフの列挙 [1] が挙げられる．しかし， いずれも強連結部分グラフの中でも特別な性質を満た す，より狭いクラスの部分グラフを列挙しており，す べての強連結部分グラフを効率良く列挙する手法は知 られていない． 提案手法はフロンティア法と呼ばれるグラフ列挙の 枠組みを用いる．フロンティア法は，与えられたグラ フに対してパスやサイクル，木・森，連結成分などの 指定された性質を満たす部分グラフを列挙する [4]．フ ロンティア法の特色は，列挙結果を Zero-Suppressed Binary Decision Diagram (ZDD) と呼ばれるデータ構 造として出力する点にある．これにより，パズルの求 ∗連絡先： 北海道大学 大学院情報科学研究科 〒 060-0814 札幌市北区北 14 条西 9 丁目 E-mail: [email protected] 解 [10] やフロアプラン [8]，配電網のロス最小化 [2] な どに応用されている． しかし，フロンティア法は多くの場合で，無向グラ フの性質を対象に用いられている．フロンティア法を 有向グラフの性質に適用した事例は，指定された 2 頂 点間の到達性を保証する性質 (Maehara ら [5]) のみで ある． 本稿では，Maehara らのアイデアに基づき，フロン ティア法を用いて強連結部分グラフを列挙する手法を 提案する．さらに，提案手法の計算量が，推移関係の 総種類数と関連があることを述べる．フロンティア法 の計算量は，与えられたグラフや列挙対象の性質に依 存するものの，ベル数をはじめとする特殊な数列に関 連する事例があることが明らかにされてきた [11]． 提案手法を用いて計算機実験を行った結果，人工デー タと実データともに効率的に処理することができた．特 に，6.5 × 1033個もの強連結部分グラフを，わずか数 分で，その個数に対して圧倒的に小さな ZDD に格納 することができており，応用上の有効性も確認できた． 本稿は次のように構成される．2 章では，準備とし て有向グラフに関する諸定義と記法，および ZDD に ついて説明する．3 章では，フロンティア法の概要と提 案手法について述べる．4 章では，計算機実験の結果 を示し，考察する．5 章で本稿をまとめる． 人工知能学会研究会資料 SIG-FPAI-B507-062
準備
2.1
用語・記法
頂点集合 V と辺集合 E ⊆ V × V からなる有向グラ フを G = (V, E) と表記する. G の頂点数および辺数を それぞれ n, m とする．辺部分集合 E′⊆ E により誘導 される頂点部分集合を V [E′] ={v | ∃(x, y) ∈ E′, x = v∨ y = v} とする．E′⊆ E および V [E′] からなる部分 グラフを G[E′] と表記する． 長さ k (≥ 2) の列 v1, . . . , vkについて，(vi, vi+1)∈ E (i = 1, . . . , k−1) であるとき，その列を v1-vkパスと呼 ぶ．G に u-v パスが存在することを u→Gv と表記し， G に u-v パスが存在しないことを u↛Gv と表記する． G が強連結であるとは，任意の頂点対 (u, v)∈ V × V に対して u→Gv が成り立つことである．2.2
強連結部分グラフの列挙
有向グラフ G の強連結部分グラフを表す辺の組合せ 全体を Gsc={E′⊆ E | G[E′] は強連結} (1) とする．本稿では，有向グラフ G が与えられたとき， すべての強連結な部分グラフを列挙すること，すなわ ちGscを生成することを考える．強連結部分グラフの 例を図 1 に示す． 強連結な部分グラフの列挙に関する研究には，Tarjan による強連結成分の列挙 [9] および Boros らによる極小 な強連結部分グラフの列挙 [1] が挙げられる．強連結成 分とは極大な強連結部分グラフのことであり，グラフ中 に高々n 個しか存在しない．Tarjan はこれを O(n + m) 時間で極めて高速に列挙するアルゴリズムを示した． Boros らは，G が強連結であるとき，全域かつ極小な 強連結部分グラフを増分多項式時間で列挙するアルゴ リズムを示した． 本稿では，Tarjan および Boros らの取り組みとは異 なり，すべての強連結な部分グラフを列挙対象として いる．すなわち，出力は強連結成分や極小な強連結部 分グラフに限らない． 図 1: 入力グラフ (左) に対する強連結部分グラフ (右)2.3
Zero-Suppressed Binary Decision
Diagram
Zero-Supprssed Binary Decision Diagram (ZDD) と は，組合せ集合を圧縮表現するデータ構造である [6]． ZDD は節点集合N と枝集合 A からなる有向グラフ Z = (N , A) で表される．2 つの終端節点 ⊤, ⊥ ∈ N が あり，これらは枝を持たない．各節点 α∈ N \ {⊤, ⊥} は 0-枝および 1-枝と呼ばれる 2 つの枝を持つ．節点 α が持つ x-枝 (x∈ {0, 1}) が指す節点を α の x-子と呼び， αxと表記する．どの枝からも指されない節点 ρ ∈ N がただ 1 つだけ存在し，それを根と呼ぶ． 今，順序付けられた辺集合 E ={e1, . . . , em} (e1< . . . < em) を扱うとする．このとき，各節点 α∈ N \ {⊤, ⊥} は，ラベル ℓ(α) ∈ E を持ち，ℓ(α) < ℓ(αx) (x ∈ {0, 1}) である．便宜上 em < ℓ(⊤) = ℓ(⊥) とす る．Z 上のパス P について， E(P ) ={ℓ(α) | P がαの 1-枝を通る } (2) とすると，P が表現する組合せ E(P ) が一意に定まる． 根 ρ から節点 α へのすべてのパスからなる集合をP(α) として， Z(α) = {E(P ) | P ∈ P(α)} (3) と表記する．このとき，Z(⊤) は Z が表現する組合せ 集合 (部分グラフ集合) そのものである． ZDD は以下の 2 つのルールによって簡約化される． 1. 各 x∈ {0, 1} について αx= βxかつ ℓ(α) = ℓ(β) であるような節点 α, β を共有する． 2. α1=⊥ であるような節点 α を削除する． この 2 つのルールは自由な順序で適用してよい．これ 以上簡約化できなくなった ZDD を既約な ZDD と呼ぶ． 既約な形は，アイテムの順序と表現する組合せ集合に 対して，一意に定まるという特徴がある．図 2 に図 1 の強連結部分グラフ集合を表現する ZDD の例を示す． 図 2: 図 1 の部分グラフ集合に対する ZDD の例
3
アルゴリズム
3.1
フロンティア法
フロンティア法は，与えられたグラフ G = (V, E) と 指定された性質 C に対して，C を満たす部分グラフの 集合を表現する ZDD ZCを構築する枠組みである [4]． 本稿では，C =「強連結である．」とし，ZC(⊤) = Gsc となるようにする． ZCにおいて，ラベル eiを持つ節点の集合をNiと 表記する．辺部分集合について，E≤i = {e1, . . . , ei}， E≥i={ei, . . . , em} とする．フロンティア法のアルゴリ ズムは，根の生成 (N1← {ρ}) からはじまり，幅優先的 に ZDD を構築していく．すなわち，i ステップ目ではNi の生成が完了しており，各節点 α∈ Niについて子節点 αxを生成する (x∈ {0, 1}) ．ノード αxを生成すると， 以下の 3 つの判定を行った後で，Ni+1← Ni+1∪ {αx} とする． 共有可能 ある辺集合 E′ ⊆ E≤iに対して，Ci(E′) = {H ⊆ E≥i+1| G[E′∪ H] が C を満たす } を定義する．ある節点 β∈ Ni+1について， ∀(E′, E′′) ∈ Z C(αx)× ZC(β), Ci(E′) = Ci(E′′) である． ⊥-枝刈り可能 各 E′∈ ZC(αx) について，Ci(E′) = ϕ で ある． ⊤-枝刈り可能 各 E′ ∈ ZC(αx) について，Ci(E′) ={ϕ} である． ここで，共有可能であるときは，α← β とする．⊥-枝刈可能であるときは，α← ⊥ とする．⊤-枝刈り可能 であるときは，α← ⊤ とする． 各操作における条件判定は，処理済みの辺と未処理 の辺の境界に位置する，フロンティアと呼ばれる頂点 集合に着目して行う．Niの節点から子節点を生成したとき，E≤iが処理済みの辺，E≥i+1が未処理の辺とな
り，そのいずれにも接続する頂点の集合 Fi = V [E≤i]∩ V [E≥i+1] がフロンティアである．3.2 および 3.3 では， C =「強連結である．」の場合について，ZCを生成す るための，フロンティアに着目した条件判定法につい て述べる．
3.2
Reachability 行列
i ステップ目に生成された各節点 α に対して，フロ ンティア Fi上に以下のような行列 R(α) を定義する． Ru,v(α) = { 0 ∀E′∈ ZC(α), u↛G[E′]v 1 ∀E′∈ ZC(α), u→G[E′]v (4) ただし，u, v∈ Fi これは，Maehara ら [5] のアイデアに基づき，より必要 な情報のみに絞ったものである．今後，このように定義 された行列を Reachability 行列と呼ぶことにする．証明 は省くが，ある節点 β∈ Ni+1について，R(α) = R(β) ならば，∀(E′, E′′)∈ ZC(α)×ZC(β), Ci(E′) = Ci(E′′) であると言え，α は β と共有してよい． 根 ρ に対する Reachability 行列 R(ρ) はすべての成 分が 0 である．ある節点 α∈ Niに対する Reachability 行列 R(α) があるとき，その子節点 αx (x∈ {0, 1}) の Reachability 行列 R(αx) は次のようにして簡単に求め ることができる．ここで，ei = (u, v) とする．はじめ に，R(αx) ← R(α) とする．x = 0 のとき，どの行， 列も変化しない．x = 1 のとき，u に辿り着ける頂点 すべてが，v から辿り着ける頂点へのパスを持つよう になるので，次の操作を行う．まず Ru,v ← 1 とする． その後，Rw,u(α) = 1 であるような w ∈ Fi に対し て Rw,v(αx) ← 1 とする．さらに，各頂点対 (x, y) ∈ Fi × Fi について，Rx,v = 1 かつ Rv,y = 1 ならば Rx,y(αx)← 1 とすればよい．また，行列の更新後は， Fi\ Fi+1に関する行と列を削除し，新たに Fi+1\ Fi に関する行と列を各成分を 0 として追加する．子節点 の Reachability 行列を求めるアルゴリズムの擬似コー ドを Algorithm1 に示す． Algorithm 1 calcReachability(i, α, x) 1: /* ei= (u, v) */ 2: R(αx)← R(α) 3: Ru,v(αx)← 1 4: for w∈ Fido 5: if Rw,u(αx) = 1 then 6: Rw,v(αx)← 1 7: end if 8: end for 9: for (x, y)∈ Fi× Fido 10: if Rx,v(αx) = 1かつRv,y(αx) = 1 then 11: Rx,y(αx)← 1 12: end if 13: end for 14: R(αx)からFi\ Fi+1に関する行と列を削除 15: R(αx)にFi+1\ Fiに関する行と列を各成分を0として 追加 16: return R(αx)3.3
枝刈り
Reachability 行列を用いて，i ステップ目に生成され た各節点 α に対して次のように⊥-枝刈りと ⊤-枝刈り を行うことができる． R(α) より，部分グラフ上で少なくとも 1 本以上の辺 と接続していると判定できる Fiの頂点部分集合をとする．さらに，R(α) から導かれる新しい辺集合 T ={(u, v) | Ru,v(α) = 1} (6) を定義する． 証明は省くが，ある頂点対 (u, v)∈ S×S について，有 向グラフ G′= (V, T∪E≥i+1) が u↛G′ v であるならば， E≥i+1の辺をどのように追加しても S を含む強連結部分 グラフは作れない．よって，∀E′ ∈ ZC(α), Ci(E′) = ϕ であり，α← ⊥ としてよい．⊥-枝刈りのアルゴリズム の擬似コードを Algorithm2 に示す． 同様に証明は省くが，⊥-枝刈りが行われなかった場 合について，S̸= ϕ かつ S ∩ Fi+1= ϕ のとき，任意の E′ ∈ ZC(α) に対して G[E′] は強連結部分グラフであ り，かつどのように E≥i+1の辺を追加しても強連結部 分グラフでない．よって，∀E′ ∈ ZC(α), Ci(E′) ={ϕ} であり，α← ⊤ としてよい．⊤-枝刈りのアルゴリズム の擬似コードを Algorithm3 に示す． Algorithm 2 isBottom(i, α)
1: S ={v | ∃u ∈ Fi, Ru,v(α) = 1∨ Rv,u(α) = 1}
2: T ={(u, v) | Ru,v(α) = 1} 3: G′← (V, T ∪ E≥i+1) 4: for (u, v)∈ S × S do 5: if u↛G′v then 6: return ”TRUE” 7: end if 8: end for 9: return ”FALSE” Algorithm 3 isTop(i, α)
1: S ={v | ∃u ∈ Fi, Ru,v(α) = 1∨ Rv,u(α) = 1}
2: if S̸= ϕかつS∩ Fi+1= ϕ then 3: return ”TRUE” 4: end if 5: return ”FALSE” 提案手法のアルゴリズムの擬似コードを Algorithm4 に示す．
3.4
Reachbility 行列の総種類数と計算量の
関係
提案手法の計算量は，1 節点あたりの計算量を O(f ) としたとき，各ステップで生成される節点数の総和を用 いて，O(f∑mi=1|Ni|) と書ける．|Ni| の明らかな上界 は，共有操作の特徴から，Fiに対する Reachability 行 列の総種類数となる．それは，頂点数 k =|Fi| のラベ ル付き有向グラフ上の推移関係の通り数 (以下，T (k) とする) に一致する．よって，計算量は最悪の場合で O(f∑mi=1T (|Fi|)) である．T (k) の詳細は，文献 [7] お よびオンライン整数列大辞典 (OEIS A006905) に見る ことができ，k = 1, . . . , 10 では表 1 のようになる． Algorithm 4 frontierBasedSearch(G) 1: N1← {ρ} 2: R(ρ)← O 3: for i = 1, . . . , m do 4: for α∈ Nido 5: for x∈ {0, 1} do 6: 節点αxを生成 7: R(αx)← calcReachability(i, α, x)8: if isBottom(i, αx) = ”TRUE” then
9: αx← ⊥
10: else if isTop(i, αx) = ”TRUE” then
11: αx← ⊤
12: else if ∃β ∈ Ni+1, R(β) = R(αx) then
13: αx← β 14: end if 15: Ni+1← Ni+1∪ {αx} 16: end for 17: end for 18: end for 19: 各節点集合Ni(i = 1, . . . , m + 1)からなるZCを既約化 20: return ZC 表 1: T (k) の値 (k = 1, . . . , 10) k T (k) 1 2 2 13 3 171 4 3994 5 154303 6 9415189 7 878222530 8 122207703623 9 24890747921947 10 7307450299510288 T (k) は表 1 の通り，k に対して急速に大きくなる． 提案手法の計算時間を削減するには，各 i = 1, . . . , m に対して|Fi| を小さくすることが重要である．|Fi| は 辺の順序付けによって変化する．maxi=1,...,m|Fi| (以 下，Fmaxと表記する) の取りうる最小値がパス幅に一 致すること，およびパス幅の近似ヒューリスティクス を用いた辺順序付けアルゴリズムが Inoue ら [3] により 示されている．
4
実験
提案手法を人工のグラフデータと実データに適用 し，その性能を評価した．計測したのは，計算時間， 構築された ZDD の節点数，既約化後の ZDD の節点数， 解の総数|Gsc|，消費メモリである．実験環境には 64-bit Ubuntu 16.04 LTS，Intel Core i7-3930K 3.2GHz CPU，64GB RAM を用いた．4.1
人工データ
はじめに，Fmaxの取りうる最小値が明らかである 2 つのグラフクラス，完全グラフとグリッドグラフで実験 を行った．n 頂点の完全グラフに対して Fmax= n−1 で， w×h 頂点のグリッドグラフに対して Fmax= min{w, h} である．完全グラフは n = 3, . . . , 9 の場合を，グリッ ドグラフは w = h で，それぞれ 2, 4, 6, 8, 10 の場合を 用いた．完全グラフは，各頂点対に双方向の辺を張り， 多重辺と自己ループがないように作成した．グリッド グラフは，偶数行と奇数行，および偶数列と奇数列に あたる辺でそれぞれ向きを変えており，多重辺と自己 ループはない．実験結果を表 2 と表 3 に示す． 提案手法により生成された ZDD の節点数は，T (Fmax) に対しては十分に小さいと言える．しかし，完全グラ フでは n = 9 で 108個の節点を越え，グリッドグラフ では w = 10 で 107個の節点を越えており，使用メモ リ量がそれぞれ 5GB，1GB となっている．特に，頂点 数が一回り少ないデータに比べて，数十倍のメモリ量 を必要としている．このことから，Fmaxが 10 を超え ると計算が難しくなると考えられる． 解の総数|Gsc| は，頂点数が多くなるにつれて急激に 増加する様子が見て取れる．しかし，|Gsc| の増加に対 する計算時間の増加は緩やかであり，提案手法の効率 は良いと言える．さらに，30 桁を超える数の強連結部 分グラフを，8 桁程度の節点数で ZDD に格納すること ができており，圧縮効率も良い．これらは，応用上と ても重要な特徴である． 表 2: 完全グラフおよびグリッドグラフでの実験結果 (計算時間と構築された ZDD の節点数，および消費メ モリ)n m time (sec) #node mem (MB)
3 6 < 0.01 31 2 4 12 < 0.01 308 2 5 20 0.02 3,171 3 6 30 0.14 36,582 4 7 42 1.87 490,759 18 8 56 34.36 7,731,791 257 9 72 812.46 142,139,720 5308
w m time (sec) #node mem (MB)
2 4 < 0.01 7 2 4 24 < 0.01 319 3 6 60 0.09 15,903 3 8 112 5.49 911,322 21 10 180 485.14 55,329,425 1006 表 3: 完全グラフおよびグリッドグラフでの実験結果 (既約な ZDD の節点数，および解の総数) n m #node |Gsc| 3 6 19 21 4 12 156 1,684 5 20 1,372 573,300 6 30 13,675 7.4×108 7 42 162,633 3.5×1012 8 56 2,299,156 6.4×1017 9 72 3,864,5318 4.4×1021 w m #node |Gsc| 2 4 4 1 4 24 189 1,557 6 60 9,429 8.4×109 8 112 552,621 1.4×1020 10 180 34,847,467 6.5×1033
4.2
実データ
次に，実データとして GraphDrawing の会議でベン チマークに用いられたネットワークのうち，井上らの 手法 [3] で Fmaxをなるべく小さくし，Fmax ≤ 10 と なった 5 つのネットワークを選択し実験を行った．使 用したネットワークとその頂点数，辺数，Fmaxの一覧 を表 4 に示す．実験結果を表 5 と表 6 に示す． 用いたすべてのネットワークに対して，高速に ZDD を構築することができた．使用メモリ量も最大で 27MB 程度である．解の総数 |Gsc| が目立つグラフは A95-Processor のみであったが，633768 個の解を 171 個の節 点からなる ZDD に格納できており，圧縮効率が良い． |Gsc| = 0 となっているネットワークに，B96-Telephone-Calls と C97-Telephone-となっているネットワークに，B96-Telephone-Calls が存在する．グラフデー タを確認したところ，これらは非巡回なグラフであり 強連結な部分グラフが存在しないことがわかった．この ようなデータに対しては，1-枝の子はすべて⊥-枝刈り されるため，生成される ZDD の節点数が m に等しい． 表 4: 実験に用いた GraphDrawing のベンチマーク name n m Fmax A95-Processor 36 56 6 B95-Program 70 95 7 B96-Telephone-calls 111 193 5 C97-Telephone-calls 452 460 4 D96-AT&T 180 228 7表 5: GraphDrawing のベンチマークを用いた実験 (計 算時間と構築された ZDD の節点数，および消費メモリ)
name time (sec) #node mem (MB)
A95-Processor < 0.01 727 2 B95-Program < 0.01 149 3 B96-Telephone-calls 0.059 193 4 C97-Telephone-calls 0.278 460 27 D96-AT&T 0.082 793 5 表 6: GraphDrawing のベンチマークを用いた実験 (既 約な ZDD の節点数，および解の総数) name #node |Gsc| A95-Processor 171 633768 B95-Program 3 1 B96-Telephone-calls 0 0 C97-Telephone-calls 0 0 D96-AT&T 28 63
5
まとめ
本稿では，フロンティア法を用いて強連結部分グラ フを列挙し，ZDD に格納する手法を示した．実験の結 果，パス幅が十分に小さいグラフにおいて，効率良く動 作することがわかった．特に，30 桁を超える数の強連 結部分グラフを，わずか数分で，圧倒的に小さな ZDD に格納できており，応用上有効であると言える． 今後の課題として，強連結成分分解を用いた高速化 を考えている．強連結成分分解とは Tarjan のアルゴリ ズム [9] を用いて，グラフを各強連結成分ごとに分解す ることである．強連結部分グラフは強連結成分の中に しか存在しないと主張ができ，与えられたグラフをよ り小さなグラフに分解して個別に解くことで高速化を 図ることができる．また，提案手法をどのような領域 に応用できるのかを検討していく．謝辞
本研究の一部は科研・基盤 (S) 15H05711 の助成に よる．参考文献
[1] E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan. Enumerating Minimal Dicuts
and Strongly Connected Subgraphs and Related
Geometric Problems, pp. 152–162. Springer Berlin
Heidelberg, Berlin, Heidelberg, 2004.
[2] Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin ichi Minato, and Yasuhiro Hayashi. Loss minimization of power distribution networks with guaranteed error bound. IEEE Transactions on
Smart Grid, Vol. 5, pp. 102–111, January 2014.
[3] Yuma Inoue and Shin-ichi Minato. Accelera-tion of ZDD construcAccelera-tion for subgraph enumera-tion via path-width optimizaenumera-tion. TCS-TR-A-16-80. Hokkaido University, 2016.
[4] Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato. Frontier-based search for enumerat-ing all constrained subgraphs with compressed repre-sentation. IEICE Trans. Fundamentals, Vol. E100-A, No. 9, to apper.
[5] Takanori Maehara, Hirofumi Suzuki, and Masakazu Ishihata. Exact computation of influence spread by binary decision diagrams. In Proceedings of the
26th International Conference on World Wide Web,
WWW ’17, pp. 947–956, Republic and Canton of Geneva, Switzerland, 2017. International World Wide Web Conferences Steering Committee.
[6] Shin-ichi Minato. Zero-suppressed BDDs for set ma-nipulation in combinatorial problems. Proc. of 30th
ACM/IEEE Design Automation Conf. (DAC 1993),
pp. 272–277, 1993.
[7] G¨otz Pfeiffer. Counting transitive relations. Journal
of Integer Sequences, Vol.7, Article 04.3.2., 2004.
[8] Atsushi Takizawa, Yushi Miyata, and Naoki Katoh. Enumeration of floor plans based on zero-suppressed binary decision diagram. In Proceedings of the 19th
International Conference on Computer-Aided Archi-tectural Design Research in Asia (CAADRIA 2014),
pp. 275–284, 2014.
[9] Robert Tarjan. Depth first search and linear graph algorithms. SIAM JOURNAL ON COMPUTING,
Vol. 1, No. 2, 1972.
[10] Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato. Finding all solutions and instances of numberlink and slitherlink by ZDDs. Algorithms, Vol. 5, No. 2, p. 176, 2012.
[11] 高野圭司. フロンティア法から生成されるZDDの幅解
