Proper Interval Graphsの ランダム生成と列挙

Slides:



Advertisements
Similar presentations
平面三角分割グラフを列挙す るアルゴリズムの改良 中野 眞一 ( 群馬大学 ) 宇野 毅明 ( 情報学研究 所 ) 2002 年 6 月 24 日 コンピューテーション研究会.
Advertisements

『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
あみだくじ AMIDA-KUJI 井上 康博 Statistical analysis on Amida-kuji, Physica A 369(2006)
A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
シミュレーション論Ⅰ 第 7 回 待ち行列のシミュレーション(2). 第 6 回のレポート(解答例) 乱数表より乱数を記入し、到着間隔・サービス時間にした がってグラフを作成する 例) 最大待ち人数:2人 最大待ち時間:5分 平均待ち時間:3分.
データの圧縮.
フロンティア法 - 組合せ問題の解を列挙索引化するZDD構築アルゴリズム
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
3.2.3~3.3 D3 川原 純.
セキュアネットワーク符号化構成法に関する研究
Bipartite Permutation Graphの ランダム生成と列挙
極小集合被覆を列挙する 実用的高速アルゴリズム
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
ラベル付き区間グラフを列挙するBDDとその応用
2分探索.
絵画的迷路の作り方 岡本 吉央 東工大 上原 隆平 JAIST.
On the Enumeration of Colored Trees
An Algorithm for Enumerating Maximal Matchings of a Graph
Permutationグラフと Distance-Hereditaryグラフの 再構築アルゴリズム
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
Probabilistic method 輪講 第7回
寺尾 敦 青山学院大学社会情報学部 エクセルでの正規分布の グラフの描き方 寺尾 敦 青山学院大学社会情報学部
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
寺尾 敦 青山学院大学社会情報学部 エクセルでの正規分布の グラフの描き方 寺尾 敦 青山学院大学社会情報学部
佐藤のゲーム とその仲間たち (完全可解ゲームの話) 関西学院大学  川中 宣明 数理科学研究センター談話会    2011年6月29日.
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
寺尾 敦 青山学院大学社会情報学部 エクセルでの正規分布の グラフの描き方 寺尾 敦 青山学院大学社会情報学部
クイックソート.
ランダムグラフ エルデシュとレーニイによって研究された.→ER-model p:辺連結確率 N:ノード総数 分布:
12. 意味・意図の解析 12.1 意味表現とは 12.2 規則による意味解析処理 12.3 統計的な意味解析処理 12.4 スマートフォンでの音声サービス ニューラルネットワークによる意味解析.
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
2018/9/10 ACL読み会 名古屋大学大学院 M2 佐藤・松崎研 土居裕典.
25. Randomized Algorithms
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
モバイルエージェントネットワークの拡張とシミュレーション
分子生物情報学(2) 配列のマルチプルアライメント法
A Simple Algorithm for Generating Unordered Rooted Trees
離散数学 07. 木 五島.
Q q 情報セキュリティ 第8回:2005年6月3日(金) q q.
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
決定木-II 学習目標 1.○与えられた事例集合から,指定された属性選択基準に基づいて決定木を生成 できる 利得 利得比
プログラミング 4 木構造とヒープ.
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
代数体上で定義された楕円曲線の 素因数分解への応用
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
第16章 動的計画法 アルゴリズムイントロダクション.
5.3, 5.4 D2 岡本 和也.
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
Max Cut and the Smallest Eigenvalue 論文紹介
情報工学概論 (アルゴリズムとデータ構造)
情報生命科学特別講義III (14) グラフの比較と列挙
4.プッシュダウンオートマトンと 文脈自由文法の等価性
ヒープソート.
Jan 2015 Speaker: Kazuhiro Inaba
オートマトンって? (Turing machine).
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
グラフの列挙 中野 眞一    (群馬大学) 2019/9/14 列挙学校.
プログラム依存グラフを用いた ソースコードのパターン違反検出法
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Time Reversal E-Text: pp.80-83(PDF: pp.49-50) FM08002 太神 諭
Presentation transcript:

Proper Interval Graphsの ランダム生成と列挙 ○斎藤 寿樹(JAIST)   山中 克久(電気通信大)   清見  礼(JAIST)(祝・結婚)  上原 隆平(JAIST)

問題(1) 連結なProper Interval Graphのランダム生成 入力:自然数 n 出力:n頂点の連結なProper Interval Graph 一様ランダムに生成 同型性を考慮 例 n=5

問題(2) すべて出力 連結なProper Interval Graphの列挙 入力:自然数 n 出力:n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく 同型性を考慮 すべて出力 例 n=5

提案アルゴリズム 連結なProper Interval Graphのランダム生成 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graph 一様ガンダムに生成(同型性を考慮) 数え上げを利用 O(n+m)時間 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく(同型性を考慮) 逆探索法を利用 1つあたりO(1)時間

提案アルゴリズム 連結なProper Interval Graphのランダム生成 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graph 一様ランダムに生成(同型性を考慮) 数え上げを利用 O(n+m)時間 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく(同型性を考慮) 逆探索法を利用 1つあたりO(1)時間

Interval Graphs Interval表現を持つグラフクラス

Proper Interval Graphs Unit Interval表現を持つグラフクラス すべてのIntervalの長さが同じ カッコ列を用いた表現

Unit Interval表現のカッコ列表現 左端点 → “(” 右端点 → “)” 左端点が現れる順番に右端点も現れる Unit Interval表現 ( ( ( ) ) ( ( ) ) ) ( ( ( ) ) ( ( ) ) ) カッコ列表現

カッコ列表現 ( ( ( ) ) ( ( ) ) ) n頂点のProper Interval Graphのカッコ列表現の特徴 1 2 3 2 “(”の数:n個    “)”の数:n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ( ) ) ( ( ) ) ) +1 +1 +1 -1 -1 +1 +1 -1 -1 -1 1 2 3 2 1 2 3 2 1

カッコ列表現 ( ( ) ) ) ( n頂点のProper Interval Graphのカッコ列表現の特徴 カッコの数:2n “(”の数:n個    “)”の数:n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ) ) ) ( ? Interval表現が書けない

カッコ列表現 ( ( ) ) ( ) n頂点のProper Interval Graphのカッコ列表現の特徴 カッコの数:2n “(”の数:n個    “)”の数:n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ) ) ( ) Unit Interval表現 グラフ表現

カッコ列表現 ( ( ( ( ) ) ) ( ( ) ) ) ) 連結なProper Interval Graphのカッコ列表現 左カッコと右カッコの数が等しいのは2箇所 左端と右端のみ 両端を除いたカッコ列がnon-negative ( ( ( ( ) ) ) ( ( ) ) ) )

カッコ列表現 Lemma 1. (X. Dell, P. Hell, J. Huang, 1996) 連結なProper Interval Graphは1つ、または2つのカッコ列表現を持つ このグラフは2つのカッコ列表現しかもたない ( ( ) ( ( ) ( ) ) ) ( ( ) ( ( ) ( ) ) ) 異なるカッコ列 Proper Interval Graph Unit Interval表現 カッコ列表現

カッコ列表現 Lemma 1. (X. Dell, P. Hell, J. Huang, 1996) 連結なProper Interval Graphは1つ、または2つのカッコ列表現を持つ このグラフは1つのカッコ列表現しかもたない ( ( ) ( ( ) ) ( ) ) ( ( ) ( ( ) ) ( ) ) カッコ列表現 Proper Interval Graph Unit Interval表現 reversible

ランダム生成アルゴリズム ( ( ( ( ) ) ( ) ( ) ) ) カッコ列をランダムに生成 Proper Interval Graphの数え上げを利用 一様ランダムにカッコ列を生成することができる ( ( ( ( ) ) ( ) ( ) ) ) reversibleなカッコ列に対応するグラフの出現確率が低い

生起確率の正規化 … … Case 1 … … … Case 2 … 一様にグラフを出力 … ( ( ) ( ( ) ( ) ) ) Sn: reversibleでないカッコ列の数 Rn: reversibleなカッコ列の数 せ い き  か く り つ せ い  き  か non-negativeなカッコ列 reversibleでないカッコ列 … ( ( ) ( ( ) ( ) ) ) ( ( ( ) ( ) ) ( ) ) … Case 1 … reversibleなカッコ列 … ( ( ) ( ( ) ) ( ) ) … Case 2 … ( ( ) ( ( ) ) ( ) ) 一様にグラフを出力 …

ランダム生成 ( ( ( ) ) ( ( ) ( ) ) ) Case 1(一様ランダムなカッコ列) 構築時間 カタラン数の一般化 Case 1(一様ランダムなカッコ列) 左から順にカッコを一つずつ生成 確率に応じて, “(” と “)” のどちらかを選択 ( ( ( ) ) ( ( ) ( ) ) ) “(” : “)” : p = C(2n’ - k, hl) q = C(2n’ - k, hr) 構築時間 カッコ列:O(n) グラフ:O(n+m) k:生成したカッコの数 h:高さ

ランダム生成 ) ) ( ) ) ) ) ( ) ) ) ) Case 2( reversibleなカッコ列) 構築時間 真ん中の高さを決める 左から順にカッコを一つずつ生成 確率に応じて, “(” と “)” のどちらかを選択 ) ) ( ) ) ) ) ( ) ) ) ) p = C(n’ - k, hl) “(” : “)” : q = C(n’ - k, hr) 構築時間 カッコ列:O(n) グラフ:O(n+m) k:生成したカッコの数 h:高さ

まとめ・今後の課題 n頂点のProper Interval Graphのランダム生成と列挙 Interval Graphのランダム生成と列挙 ランダム生成:O(n+m)時間 列挙:1つあたりO(1)時間 高々n頂点に拡張できる Interval Graphのランダム生成と列挙