スライド 1

ラベル付き区間グラフを
列挙するBDDとその応用
○斎藤寿樹（ERATO・BDD/ZDD普及協会）
湊真一（北海道大学，ERATO・BDD/ZDD普及協会会長兼務）
夏のLAシンポジウム
2010年7月20日
区間グラフ
• 区間表現を持つグラフクラス
▫ 区間の集合
▫ 各区間は頂点と対応
▫ ２つの区間に重なりがある
⇔ 対応する頂点間に辺がある
多くのアルゴリズムが存在
提案されたアルゴリズムが実装上高速か？
計算機実験
入力
出力
一様ランダムにデータを生成
区間グラフ
単純な区間グラフのランダム生成法
• 区間をn個ランダムに生成
▫ 区間[0, 1]におさまるような，区間をn個ランダムに生成
1
０
区間グラフは一様に出力されていない
密なグラフが生成されやすい
本発表：BDDを使って，連結なラベル付き
区間グラフを一様ランダムに生成
BDD (Binary Decision Diagram)
• 論理関数をグラフで表現
x1
x2
x3
F
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1
x1
x2
x2
x3
1
x3
0
1
x3
0
1
x3
0
1
1
x1
x2
x3
0
1
ＢＤＤを用いると
・列挙
・数え上げ
・ランダム生成
・etc.
n頂点のすべての区間グラフを表現するBDD
• 論理変数ei, j を用意(1≦i<j≦n)
1
ei , j   辺(i, j)を使う
0 辺(i, j)を使わない
• 論理関数 F
1
F (e1, 2 , e1,3 ,, en 1,n )  
0
1
3
区間グラフ
区間グラフではない
1
3
5
2
4
区間グラフ
F(1,1,1,0,0,1,0,1,1,1) = 1
5
2
4
区間グラフではない
F(1,1,0,0,0,1,0,1,1,1) = 0
n頂点のすべての区間グラフを表現するBDD
• 論理関数 FのBDD
▫ 例：n=5
0
0
１
１
0
e1,2
１
e1,3
e1,4
・
・
・
e4,5
0
1
BDDを用いた区間グラフのランダム生成
• ランダム生成アルゴリズム
(Knuth, the art of computer programming, vol. 4.1)
1. 解の数を数える
541
 BDDをボトムアップに探索
2. 変数に{0, 1}を割り当てる
 トップダウンに割り当て
 “偏った”コインフリップ
303
238
102
35
136
67 67
136
69 67
167
69 69
 解の数の割合
n頂点の区間グラフを
ランダム生成できる
0
1
98
構築したBDDの応用
• n頂点の区間グラフのランダム生成
▫ 辺の数や次数を制限したものもランダム生成できる
∧
0
1
5頂点のすべての区間
グラフを表現するBDD
1
0
辺の数が6以下のすべて
のグラフを表現するBDD
0
1
頂点数が5で，辺の数が
6以下のすべての区間グ
ラフを表現するBDD
構築したBDDの応用
• n頂点の区間グラフのランダム生成
▫ 辺の数や次数を制限したものもランダム生成できる
• 区間サンドイッチ問題(NP-完全問題)がBDDサイズ
の線形時間で解ける
区間グラフのBDDの構築手法
• 区間グラフを列挙
▫ 効率のよい列挙アルゴリズム [清見, 来嶋, 宇野, 2006]
▫ グラフの数は指数個
時間がかかる！
e1,2
e1,3
1
3
e1,4
5
2
∨
e1,5
4
・
・
・
出力したグラフ
e4,5
0
0
1
1
構築中のBDD
区間グラフのBDDの構築手法
• 区間グラフを列挙
▫ 効率のよい列挙アルゴリズム [清見, 来嶋, 宇野, 2006]
• 論理関数Fを論理式で表現
▫ 論理変数のみを用いて，区間グラフの認識を行う
簡単にはできない
最も単純なアルゴリズム：LexBFSを用いたアルゴリズム
(Corneil, et. al., SODA, ’98)
計算機実験
• 区間グラフを列挙して，BDDを構築
• 計算機環境
▫ CPU
頂点数
 Quad-Core 3.1GHz
区間グラフ
の数
BDDの
ノード数
計算時間
(sec)
▫ Memory
3
4
4
0.08
 528GB
4
35
18
0.11
5
541
114
0.60
6
13062
1259
9.56
7
444767
17194
50
8
19912657
246630
3158
9
11121041222
3938791
269971
▫ プログラミング言語
C
▫ BDDパッケージ
 BemⅡ
約2800倍
約3日強
計算機実験
頂点数 7 辺の数m以下（x軸）
・区間グラフの数
・BDDのサイズ
計算機実験
ノード数：650712
(約12 Mbyte)
BDDサイズの変化 (n=8)
今後の課題
• 区間グラフを表現するBDDについて
▫ 区間グラフを列挙せずに構築可能か？
 区間グラフの認識を論理変数のみで行えるか？
 n-1頂点のBDDを使って，n頂点のBDDが作れないか？
 区間を論理変数で表現する？
▫ 非連結な区間グラフのBDD
• BDDを構築しないで、区間グラフのランダム生成
▫ 解の数を数える手法の考案
• ラベルなしグラフのランダム生成
▫ どのようにBDDの表現するか？
辺の数m 辺の数m以下の
区間グラフ数
BDDの
ノード数
辺の数mの区 BDDの
間グラフ数
ノード数
6
15967
1718
15967
1718
7
48202
5015
32235
4614
8
98497
8959
50295
7536
9
169302
12393
70805
9257
10
246372
15733
77070
10832
11
314643
17840
68271
10684
12
365848
18764
51205
8859
13
403018
18991
37170
6807
14
425908
18753
22890
4945
15
437283
18302
11375
3192
16
442155
17726
4872
1807
17
444045
17434
1890
899
18
444640
17316
595
431
19
444745
17225
105
141
20
444766
17201
21
40
21
444767
17194
1
21
頂点数7
辺の数を制限した
ときのグラフの数
とBDDのサイズ
計算機実験
次数d
すべての頂点の次数がd以下の BDDのノード数
すべての区間グラフの数
6
444767
17194
5
334740
16757
4
151410
11892
3
40320
5494
2
2520
1350
頂点数7 次数を制限
・グラフの数
・BDDのサイズ

Download Report