区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム北陸先端科学技術大学院大学（ＪＡＩＳＴ）情報科学研究科斎藤寿樹清見礼上原隆平発表内容  区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム 1 1 2 9 3 4 5 10 6 7 12 2 2, 4 4 9 3 5 6 10 11 11 8 7 区間表現 8 MPQ-tree 12 区間グラフとは  1950年代後半に数学者の Hajös と，分子生物学者の Benzer とが独立に考えたグラフクラス  区間表現をもつグラフ   0 それぞれの区間は各頂点に対応 2つの区間が重なっている ⇔ 対応する2つの頂点間に辺が存在する 1 2 3 4 5 6 1 I3 3 I4 I1 I2 2 4 区間グラフの応用  区間をDNAの断片や時間と考える  バイオインフォマティクス数十万～数百万の区  スケジューリング問題など間を処理高速なアルゴリズムが必要 x1 x2 x4: TTTACGTGGT x3 x4 断片の文字列区間グラフ x1: ACGGTTTA x2: ATCGGAACG x3: AACGGTTTAC ATCGGGAACGGTTTACGTGGT x2 x1 x3 x4 区間表現 PQ-tree  1976年にBoothらによって提案  区間グラフ用の補助データ構造木構造(順序木)  内部ノードにはPまたはQのラベル  葉には極大クリークを割り当てる  O(n)領域  区間グラフの認識(O(n+m)時間) ○：Pノード □：Qノード  C7 C1 C5 C6 C2 C3 C4 PQ-tree MPQ-tree(Modified PQ-tree)  1989年にKorteらによって提案  区間グラフを表現するデータ構造  PQ-treeの改良  各ノードに頂点集合を割り当てる  O(n)領域  区間グラフの認識  区間グラフの同型性判定（O(n+m) 時間） ○：Pノード □：Qノード 1 2 2, 4 4 3 5 6 12 9 10 7 8 MPQ-tree 11 MPQ-tree  葉およびPノードとQノードと呼ばれる節点を持つ順序木  Qノードはセクションと呼ばれるまとまりに分割  Pノードとセクションに頂点集合を割り当てる  根から葉までのパス上に存在する頂点集合は区間グラフ上で極大クリーク Qノード Pノード 4 1 2 2 2, 4 4 9 5 5 10 11 6 :Q-node 10 12 11 :P-node 7 8 MPQ-tree 6 1 3 3 7 12 9 葉区間グラフ 8 MPQ-tree  葉およびPノードとQノードと呼ばれる節点を持つ順序木  Qノードはセクションと呼ばれるまとまりに分割  Pノードとセクションに頂点集合を割り当てる  根から葉までのパス上に存在する頂点集合は区間グラフ上で極大クリーク Qノード Pノード 4 1 2 2 2, 4 4 9 5 5 10 11 6 :Q-node 10 12 11 :P-node 7 8 MPQ-tree 6 1 3 3 7 12 9 葉区間グラフ 8 MPQ-tree  区間表現と密接な関係がある  MPQ-treeの親は区間表現において子を内包 1 1 2 2 3 3 9 9 2, 4 4 4 5 5 10 10 6 6 7 7 8 8 12 12 11 11 MPQ-tree  区間表現と密接な関係がある  MPQ-treeの親は区間表現において子を内包 1 1 2 2 3 3 9 9 2, 4 4 4 5 5 10 10 6 6 7 7 8 8 12 12 11 11 MPQ-tree  対応する区間グラフが変化しない操作 1. 2. Pノードの子の順序を任意に入れ替える Qノードのセクションの順序を逆順にする 1 1 2 4 2 4 9 5 6 10 11 7 5 12 9 11 7 8 1 3 3 6 2, 4 10 2 12 5 3 10 11 12 12 11 6 7 8 8 1 9 10 4 9 1 2 2, 4 3 4 10 7 11 12 2 4 3 6 5 9 5 6 7 8 8 今回の問題について  入力:区間表現  出力: MPQ-tree    応用上の多くの問題の入力は区間表現入力される区間の数は大量構成する既存のアルゴリズムは複雑  グラフ表現経由  直接（PQ-tree用）効率がよく単純なアルゴリズムは重要既存の手法(グラフ表現経由)  グラフ表現から構成 O(n+m)時間かかる区間表現をグラフ表現に変換グラフ表現からMPQ-treeを構成 1. 2. 区間表現 1 O(n)領域 O(n+m)時間 O(n+m)領域 9 10 4 5 6 7 12 11 2 8 O(n)領域 1 6 7 5 8 1 3 MPQ-tree O(n+m)時間 4 2 3 2 グラフ表現 1 場合分けが多く実装が複雑 12 9 11 10 2 3 2, 4 4 9 5 6 10 11 7 8 12 既存の手法(区間表現からPQ-tree)  区間表現から直接PQ-treeを構成    O(n log n)時間端点がソートされているときO(n)時間 decomposition tree という概念を使用するため複雑 1 2 9 3 10 4 5 6 7 8 区間表現 O(n)領域 12 11 C7 O(n log n)時間 C1 C5 C6 C2 C3 C4 PQ-tree O(n)領域提案手法  区間表現から直接MPQ-treeを構成    O(n log n)時間端点がソートされているときO(n)時間単純なデータ構造（スタックなど）を用いたアルゴリズム 1 1 2 9 3 10 4 5 6 7 8 区間表現 O(n)領域 12 11 2 O(n log n)時間 3 2, 4 4 9 5 6 10 11 7 8 MPQ-tree O(n)領域 12 提案手法冗長性がある 3 2 区間表現 12 10 1 4 9 6 7 5 O(n)時間 11 8 コンパクトな区間表現 1 2 区間をP/Qノードおよび葉に分類 MPQ-tree 12 9 3 10 4 5 11 6 7 8 冗長性がない番号は規則を持つ提案手法 1 区間表現 2 12 9 3 10 4 5 11 6 O(n)時間 7 8 コンパクトな区間表現 1 O(n)時間区間をP/Qノードおよび葉に分類 O(n)時間 MPQ-tree 2 2, 44 2, 4 3 5 6 7 12 9 10 8 11 区間をP/Qノードおよび葉に分類  葉に分類される区間   Qノードに分類される区間   区間の長さが0 他の異なる区間と互いに一部分だけ交差 Pノードに分類される区間  その他の区間区間をP/Qノードおよび葉に分類  左から端点をスイープ  左端点iLを読み込んだとき PUSH(S,iL)  右端点iRを読み込んだときスタックの先頭とiを比較  整合性が取れていなければQノード例 1 一致しない 2 3Ｌ 3 2Ｌ 1Ｌスタック 1R 整合性が取れていないのでQノード区間をP/Qノードおよび葉に分類  左から端点をスイープ  左端点iLを読み込んだとき PUSH(S,iL)  右端点iRを読み込んだときスタックの先頭とiを比較  整合性が取れていなければQノード例 1 2 3Ｌ 3 2Ｌ 1Ｌスタック 2R 区間をP/Qノードおよび葉に分類  右の端点iRを読み込んだとき  Qノードに分類されている区間の右端点がすべて読み込まれたとき  Qノードをスタックから取り除き、確定する例 1 2 3Ｌ 3 2Ｌ 1Ｌスタック 3R 1,2,3 Qノードに確定区間をP/Qノードおよび葉に分類  右の端点iRを読み込んだとき   スタックの先頭とiが異なるQノード Qノードをマージ例 1 5Ｌ 2 34R 4Ｌ 3 3Ｌ 4 5 2Ｌ 1Ｌスタック 12R 区間をP/Qノードおよび葉に分類  同じQノードに含まれる区間はスタック上で連続に存在 iR O(1)時間マージの回数は全体で高々n回 O(1)時間 iL アルゴリズムの実行時間 … O(n)時間結論  区間表現からMPQ-treeを構成するアルゴリズム  O(n log n)時間で実行できる  ソートされていればO(n)時間  単純なアルゴリズム今後の課題  区間グラフの列挙（ランダム生成）  高速であることを実験的に示す