数理解析研究所講究録
第 1554 巻 2007 年 93-10093

区間表現から MPQ-tree を効率よく構成するアルゴリズム
斎藤寿樹

清見礼

上原隆平

北陸先端科学技術大学院大学情報科学研究科

1

はじめに

区間グラフは 1950 年代の後半に数学者のと, 分子生物学者の Benzer とが独立に考えたグラフクラスである [1]. あるグラフ $G=(V, E)$$Haj\propto$$(|V|=n, |E|=m)$ が区間グラフであるとは,$V$の各頂点を数直線上の区間に対応付けることがで
き, $V$ の頂点が隣接することの必要十分条件が,対応する区間が重なりを持つときである. この区間の集合を区間グラフの区間表現という. 区間グ
ラフは一つの区簡を時間. 温度などと考えることにより, 様々な応用がある. 特に. バイオインフォ
マティクスにおいて. DNA の断片を一つの区間と考えることができる. このような区間グラフの笑際の応用では, 多くの場合区間グラフは区間表現が入力として与えられることが想定される.
$MP\not\in trae$ は区間グラフの認識のために考案されたデータ構造で, $PQ$.tree を拡張して得られる[2]. $MP\not\in trae$ は区間グラフの同型性の判定に用いることができる. またそれをもとに高速に復数の区間表硯を作ることができ, $O(n)$ 領域で表現できるコンパクトな構造である. このように $MP\phi$tree は区間グラフの応用に有用なデータ構造でまた, スタック操作を中心とした単純なアルゴリズムで, 実装も容易である.

本アルゴリズムの概要は次の通りである. (1)
入力された区間表現から冗畏性を含まず, 番号付けもある規則を満たすコンパクトな区間表現を求める. (2) コンパクトな区間表現から $MPQ$.treeを構成する.

2

準備

2.1

区聞グラフ

グラフ $G=(V, E)$ に対し, 数直線上の区間の集合 $\{I_{v}|v\in V\}$ が存在し, 以下を満たすとき,は区間グラフであるという [1]. すなわち$\forall v_{1},v_{2}\in V,$ $(v_{1},v_{2})\in E\Leftrightarrow I_{v\iota}$$I_{v_{2}}$は共通部分を持つ.
を $G$ の区岡表現
このような区閥の集合という. 本論文において. それぞれの区間は閉区の閥とする. つまり, 区間の右端点と区間$\{I_{v}\}_{v\in V}$$I_{v}$$I_{u}$

左端点が数直線上の同じ値に存在するとき. 2 つの区間は共通部分をもつ. 区間グラフと対応する区間表現の例を図 1 に示す.

ある.

$\}\infty^{I}-$

既存のアルゴリズムを用いて, 区間表現を入力として MPQtree を構成する手順を示す.と$G$$\underline{I_{c}}$Korte$\vdash^{A}\dashv I\underline{I_{d}}$と M6ring の論文 [2] では,2 通りの $MP\phi tree$ の構成法を示している魁 どちらも入力はグラフで

図 1: 区間グラフと対応する区間表現ある. したがって, グラフ $G=(V, E)$ から $MP\not\in$trae を構成するには, 本質的に $O(n+m)$ 領域と$O(n+m)$ 時間かかる. また, どちらも多くの場合分け力泌要であり, 線形時間といっても非常に摸雑なアルゴリズムである.
本論文で}$ 区間表現を入力として与え, MPQtree を直接構成する. このアルゴリズムはグラフ表現を用いず. $O(n)$ 時閥 $O(n)$ 領域で動作する.

2.2

区聞表現

1 章で述べたように, 現実の問題では笑際のデータを元にした区間表現 (時間軸や DNA の文字列など) が入力として与えられることが多い.

本論文では次のような区間表現を入力として扱う.

94
1. 各区間の端点は数直線上の整数点に存在する.
2. 榎数の端点が同じ整数点上に存在しない.
この区間表現には冗長性が存在するため, この区間表現を冗長な区間表現と呼ふ 図 2(a) は冗長な区間表現の例である.
区間 に対し, 次の値を定義しておく.

トな区間表現ということにする. この左端点優先の長さ順序のコンパクトな区間表現を用いると,$MP\phi tree$ の構成を単純にすることができる.

以下を定義する. 相異なる 2 つの区間
$x,y$ の端点がここで,$l(x)<l(y)\leq r(x)<r(y)$ または $l(y)<$$x$

1. $l(x)$ : 左の端点が存在する数直線上の値
2. $r(x)$ : 右の端点が存在する数直線上の値
3. length $(x)$ : $k$ 間 の長さ $(r(x)-l(x))$$l(x)\leq r(y)<r(x)$$x$

先ほど述べたように, 入力として与える区間表
現には冗長性が存在するため, 処理が複雑になってしまう. そこで, 冗長性のない区間表現に変換する.
ここでコンパクトな区問表現を定義する. 整数
点 を含む区間の集合を $N[i]$ とする. それぞれの(a)(b)
図 3: 部分交差$i$

区間の端点が 1 から始まる連続した整数点上に存在し,2.3$P\sim tree$ と $MP\psi tree$

は区間グラフを認瓢するために導入されたデータ構造である [4]. $PQ\cdot trae$ は与えられたグラフ $G=(V, E)$ を表すためのデータ構造である. $P\phi trae$ は $P$ ノードとノードの 2 種類の内部ノードを持つ順序木で. 以下を満たすものとして定義される. (1) ノードの子の数は 3 以上である. また. 葉はラベルを持つ. (2) 区間グラ$P\phi tr\infty$$N[i]\backslash N[i+1]\neq\phi$

かつ $N[i+1]\backslash N[i]\neq$$\phi$

が各整数点 について成り立つとき, この区間表
現はコンパクトな区間表現であるという. 図 2(b)は (a) に対応したコンパクトな区間表現である.
$i$$|a4\ovalbox{\tt\small REJECT}$$\prime 2*||||\cdot|\ovalbox{\tt\small REJECT}^{\tau a\tau\prime*1u}$$\underline{1}\underline{i}$

フ $G$ に対応する $P\psi trae$ において,$T$の葉のラ$H’H^{6}$$a|H^{l}\uparrow$

る. (3) $PQ$.troe $T$ に肘して,次の 2 つの操作を有限回当てはめることで, 他のを得た$T’$$G$もとき,に対応する $P\phi tree$ である. さらに. $G$ に対応する任意の $P\phi traeT’’$ はこの操作$PQ\cdot t_{1}\cdot aeT’$

$7|$
$|$

(a)

(b)

図 2: 冗長な区間表現と対応するコンパクトな区間表現
区間の番号に対して, 一定の規則を仮定できると, 構成アルゴリズムを単純化できる. そこで,次の規則で区間の番号付けを行う.

.

2. $l(x)=l(y)b’\supset l\epsilon ngth(x)>length(y)fg$
らば $x<y$$Q$

ベルは $G$ の極大クリークと 1\iota 寸 1 に対応してい$H\underline{*}r^{l}|\underline{H}$

1. $l(x)<l(y)$ ならば $x<y$$Q$.

このような順序に番号を付け替えたコンパクトな区間表現を左端点優先の畏さ順序のコンパクで $T$ から得られる.

ノードの子の順序を任意に入れ換える.
ノードの子の左右の順序を逆にする.
$MP\phi tr\infty$ (Modified PQtree) は $PQ$ .trae を拡張したデータ構造である [2]. $MP\not\in troe$ を用いることで, 入力の線形時間で区間グラフの同型性判定を行うことができる $[2][5]$ また $MPQ\cdot trae$ を用いて与えられた区間グラフに対応するすべての区閥表現を作り出すことができる.
$MP\phi trae$ は $PQ\cdot trae$ から次のように構成されるデータ構造である. $T$ を区間グラフ $G=(V,\dot{E})$に対応する $P\phi trae$ とする. このとき, $T$ の葉に1.
2.

$P$$Q$.

95
は $G$ の極大クリークのラベルが存在する.

1.

$A\cdot IP\phi$

は $T$ の各ノードに対し. 次の規則で頂点treeの集合を割り当てることで構成される.
ノードに関して,は,における1.のすべての部分木に存在する極大クリークに含まれ, かつ $T$ の部分木以外の極大クリークに存在しないすべての頂点のラベルを持つ.
ノード
におけるに関して.
2.の子供$T^{*}$$P$$\hat{P}$

$Q$

$T$

$\hat{P}$$Q_{1},$の部分木を処とする. それぞれのして,$\ldots,Q_{k}$$T^{*}$とし $(k\geq 3),$

$Q$

$Q_{1}$,4.に対をにセクションと呼ばれる集合割り当てる. セクション
は.の極大クに含まれ, かつ でリークと他の部分木$T$はない他の の部分木に存在している極大クリークに含まれていないすべての頂点のラベルを持つ.
このようなラベル, セクションの割り当ては必ず存在し, $P\phi tree$ と $MP\phi tree$ は 1 $1V1$ に対応することが容易に確認できる.
図 4(a) は区間グラフである. (b) は (a) に対応$\hat{Q}$$S_{i}$$S_{i}$$v$

れる.

: を根としたを$O(n)$$T^{*}$$\hat{Q}$$T$

は $O(n+m)$ 時閥で得ることができ,領域で表現できる.の根から
2. $G$ のそれぞれの極大クリークは葉までのパス上に存在する頂点ラベルの集合の 1 つと一致する.
において. $G$ の頂点 は 1 つの葉, また
3.
は 1 つの $P$ ノード, または 1 つの $Q$ ノードの 2 つ以上連続したセクションに 1 回だけ現$\hat{P}$$T$$\hat{Q}$$T^{*}$の根は全ての極大クリークに屑している頂点を含む. また, 葉は単体的頂点を含む.

$T^{r}$$T_{i}$$\hat{Q}$$\tau_{j}$$MP\psi trae$の各セクションやそのセクションの部分木には次のような規則が存在する.
$\sqrt 2$.

を $MP\not\in trae$ の $Q$ ノードとする.

$[2][3]\hat{Q}$$\ldots,S_{k}$ の順であるとし,のセクションをまたを $S_{i}(1\leq i\leq k)$ より下の部分木に存在する$\hat{Q}$$S_{1},$$U_{i}$

頂点の集合とする. このとき, 以下の性質が成り立っ.

1. $S_{1-1}\cap S_{1}\neq\phi(2\leq i\leq k)$ ,かつ,2.
かつ,
3.
かつ
4.
$(2\leq i\leq k-1)$ ,5. $S_{i-1}\neq S_{1}(2\leq i\leq k)$ ,する $P\not\in trae$ であり, (C) は (a) に対応する $MP\phi$$s_{k}\subseteq s_{k-1}$$S_{1}\subseteq s_{2}$troe である.

$U_{1}\neq\phi$$U_{k}\neq\phi$$(S_{i}\cap S_{i+1})\backslash S_{1}\neq\phi$6.

$c_{1}=c_{2}=f_{1,3,4}^{1,2,4}i$$(S_{i-1}\cup U_{i-1})\backslash S:\neq\phi$$(2\leq i\leq k)$.

$(S_{1-1}\cap S_{1})\backslash S_{k}\neq\phi$

かつ$(S_{i}\cup U_{1})\backslash S_{i-1}\neq\phi$$C_{6}=C_{4}^{3}=C=\{\begin{array}{l}4,74,6\iota\end{array}$3

コンパクトな区問表現の構成

3.1

コンパクトな区間表現の構成

まず, 冗長な区間表現のデータ構造を示す. 入力

として与えられる冗長な区間表現 $RI$ は実際のデータの各端点を順番に並べたものである. $RI$ は端点(b)図 4:(c)

グラフとグラフに対応する $P\phi tree$ と$MP\phi trae$$MPQ\cdot trae$には次の性質がある.

定理 1. $[2][3]T^{*}$ を区閥グラフ $G=(V. E)$ から与えられた $MP\phi trae$ とする.

が区闇表現の左にあるものから順に双方向連結リストで格納されると仮定する. 双方向連結リストの最初の端点を head $(RI)$ で与える. 各端点は区間の番号 $1=\{1, \ldots,n\}$ ) と端点の種類 $(=\{L,R\})$の 2 組のデータを持つ.
次に, コンパクトな区間表現のデータ構造を示す. コンパクトな区間表現の最大の整数点をmax.CI とする. このとき, コンパクトな区間表

96
現は $mcCI$ 個の要素を持つ配列 C 町 1.. $maxCI$ ] である. 添字は区間表現の整数点であり, 配朔の各まず番号の小さい順に左端点を格納する. 次に番号の大きい順に右端点を格納する.

要素はその整数点上に存在する端点の連結リストである. 各端点は区間の番号と端点の種類の 2 組のデータを持っ.
コンパクトな区間表現をこのようなデータ構造

ここでコンパクトな区間表現 $CI$ を入力とし,左端点優先の長さ順序のコンパクトな区間表現
LLorderCI を出力するアルゴリズムについて説明にするとスイーブがしやすくなる. スイーブとはを行う. このときどの区間も左端点から読み込ますべての整数点の端点を 1 通り読み込む処理である.
次のようにして, 冗長な区闇表現 $RI$ をコンパクトな区間表現 $CI$ に変換する. まず, $RI$ の端点を左から順番に読み込んでいく. $RI$ の連続する 2つの端点が次の順に現れるとき, $CI$ では 2 つの端点は同一整数点上に存在する.

れる.

1. 左の端点
2. 左の端点

3. 右の端点$arrow$$arrow$$arrow$

右の端点左の端点右の端点それぞれを図示すると, 図 5 の (a), (b), (c) のときである.

$-\mapsto$$\mapsto\mapsto$

(a)

(b)

$–$する. このアルゴリズムは $CI$ に対してスイープ

スイーブが CI $[i-1]$ の端点をすべて読み込んだとする. また, ここまでに読み込んだ左端点の数をとする. $CI[i]$ を見たとき, $(x_{1}, L)arrow$$h$の順で左の端点が格納さが $h+1$ 個目に読み込まれた左端点であるので, LLorderCI の左端点は$(h+1,L)arrow(h+2, L)arrow\cdotsarrow(h+k,L)$ の順番に格納される. 図 7 はその様子である. 図の (a)は $CI$ であり, (b) は LLorderCI である.
$(x_{2}, L)arrow\cdotsarrow(x_{k}, L)$れていたとする.

$(x_{1}, L)$$[i]$$\frac{i}{\ovalbox{\tt\small REJECT}_{(h+1}}L$$\frac{m^{i}}{(x_{11}^{l},L)}$)$(x_{2,1}, L)$–$(h^{1}+2, L)|$(c)$(h^{\dot{\mathfrak{l}}}+k, L)|:$$(x_{\mathfrak{l}^{k}}, L)i:$

図 5: 同一整数点上に存在する端点$(y\dagger^{R)}$左の端の連続する 2 つの端点が右の端点点のとき, $CI$ では 2 つの端点は同じ整数点上にの右の端点と存在しない. 図 6 のようなとき,の左の端点は同じ整数点上に存在しないように,整数点をシフトさせ, 端点を格納する.
$RI$$arrow$$x$:(a)
図 7: 左端点の格納$y$–$\mapsto$(b)

ある区間の左端点 $(x_{a}, L)$ が $CI[i]$ に存在し, 右端点 $(x_{a}, R)$ が] に存在したとする $(i\leq j)$は $h+1,$ $\ldots,h+k$ のうちのいずれかこのとき,である. 左から端点を読み込んでいくので, 区間の長さが短い順に 号を付けることが簡単である.
LLoderCI から, 左端点が同じ整数点上に存在するとき, 区闇は長さの短い方から大きい番号を付ける. よって, CI $[i]$ に左端点が存在する区間は右$h+1$
端点を読み込まれた順に $h+k,$ $h+(k-1),$
は $h+b$ に香号付けさの号を付ける. そして,れるとき, $h+b$ の右端点が に存在していたことを配列 EristR に格納しておく. スイープが終わっ.

$CI\lfloor;$$x_{a}$図 6: 同一整数点上に存在しない端点

3.2

左端点優先の長さ順序のコンパクトな区間表現の構成

左端点優先長さ順序のコンパクトな区間表現のデータ構逍はコンパクトな区間表現と同じである.
さらに, コンパクトな区間表規のデータ構造のリストの格納順の規則を与える. 1 つの整数点上で,$\ldots,$$x_{a}$$j$97てから,ExistR を後ろから参照して, LLorderCIの区間の番号の大きい順から右端点を LLorderCIに格納していく. その様子を図 8 に示す.

41 節で区間を $P$ ノード,ノ $-$ ト,葉に分類するアルゴリズムについて記述し, 4.2 節で分\hslashされたノードの親子関係を築くアルゴリズムについて記述する.

4.1

$Q$

区問を属するノードに分類するアルゴ
リズム

図 8: 区問の番号付け

4$MP\sim tree$の構成$n$

本章では MPQtree を構成する手順について述
べる. $MPQ$ .tree には $P$ ノード, $Q$ ノート, 葉が存在する. 本章において, 葉は子を持たない $P$ ノードとして扱う. まず, 3 章のアルゴリズムを用いて,入力の区間表現を左端点の長さ順序のコンパクトな区間表現 $LLord\epsilon rCI$ に変換する. 次に,
LLorderCI を入力とし, 次の 2 つのアルゴリズムを用いて $MP\not\in tree$ を構成する.

1 つ目のアルゴリズムは,$LLord\epsilon rCI$を入力として,それぞれの区間が属するノードとその種類( ノードか ノードか) を表す配列加 minarA を$P$

$Q$作成する. このアルゴリズムは図 9 の (a) の区闇表現 $LLod\epsilon rCI$ から (b) のノードを作成する.

2 つ目のアルゴリズムで. 作成した加 minarAと入力の LLo rderCI を用いて, $MP\not\in tree$ を構成する. このアルゴリズムでは分類結果の情報を元に, それぞれの $P$ ノードや $Q$ ノードの親子関係を築き,の構造を構成する. 図 9 の (c)は (a),(b) の情報を元にして, 親子関係を築いた$MP\phi trae$ である.

$H$a

方の端点が読み込まれた区間のことを完全な区間という. また, このアルゴリズム 1 は区闇がどのノードに分類されるかがわか\sim たとき, その都度分類を行う. そこで. 不完全な区闇が存在するノードのことを不完全なノードと呼ぴ, 完全な区間しか存在しないノードを完全なノードと呼ぶ.
アルゴリズム 1 は次の定理 3 の性質を用いて,同じノードに分類される区間を見つける.
$Q$

定理 3. コンパクトな区閥表現において, 区間と が部分交差しているとき,と の区間の香号は同じ ノードに分類される. また, 区間 と
$x$

$y$

$Q$

$y$

$x$

が $Q$ ノードに分類されるとき, $l(x)=l(z)$ か$r(y)=r(z)$ となるような区間$Q$ ノードに分類される.

っ$z$の番号も同じ

スタヅク $S$ に対して次の操作を行い, 部分交差している区間を見つける. まず, スイープで区闇$O^{1}$$|$

6の左端点を読み込んだとき, Push $(S,x)$ を行う.
区間 の右端点を読み込んだとき, $S$ の先頭の要が $S$ に格納されている区闇素と を比較する.と部分交差しているとき, $S$ の先頭の要素と は$x$$7|$(a)$x$$y$$AfP\phi trae$$\frac{1}{34l}$$|$

区闇を各ノードに分類するアルゴリズムをアルゴリズム 1 に示す. . このアルゴリズムの入力は左端点優先のコンパクトな区間表現 LLoderCI であり, 出力はそれぞれ区悶が眉するノードとその種類を表す配列 $Lam,\dot{m}arA$ [1..n] である. は入力の区間の数である.
アルゴリズム 1 はスイーブを 1 回行う. スイー
プを行うと, 任意の区間は右の端点より先に左の端点が読み込まれる. スイープの途中で, 左の端点を読み込み, 右の端点を読み込んでいない区間を不完全な区間という. それに対し, 左と右の両

$Ol7$

$x$

(b)

(c)

$x$

$x$

$x$

図 9: アルゴリズムの流れ一致しない. そして,ている$S$の先頭から が格納されの要素までに現れる区間の香号はすべて
$S$

$x$

98

Algorithm 1: 区間を各ノ $-$ ドに分類するアルゴリズム

Input: 左端点優先の長さ順序のコンパクトな区間表現 $LLord\epsilon rCI$
Output: 属するノ $-$ トと種類を表す配列

LaminarA
1 for $i=1$ to maxCI do2(a)図 10: 同じ $Q$(b)
ノードに分類

(c)

$s$

4

ノードがすでに不完全なに分類されているとする. ここで. 区間 の右端点が読み込まれたとき, スタヅクの先頭からに含まれる区闇を同一の $Q$ ノードに分類する. このとき,スタックの先頭と の間に 以外の不完全なノードとはマーが存在したとすると,ジされ, 軌に分類されている区間はと同じ $Q$ノードに分類される.
マージの回数を求めるため, マージ闘係を表すの葉を区間と考える木を用いる (図 11).と, 葉の数は 個である. 1 回のマージ操作が 1つの内部ノードに対応させると. 内部ノードの数は高々 であるので, マージを行う回数は高々ノ $-$ トをマー回である. また. 2 つの不完全なジするとき, 2 つのノードのスタヅクでの添字の範囲を格納しておくことで, マージにかかる時問は $O(1)$ で可能である. よって, 全体のマージは

区間

$Q$

$x$

$\hat{Q}$$x$$\epsilon$$\tau$$\hat{Q}$$x$$\hat{Q}$$\hat{Q}$8$T_{m}$$\epsilon\neq NIL$

aの先頭から num までが同じノード;
if 不寛全な $Q$ ノードが完全に$S$

9なる then
10

$S$

$n$

$Q$

$O(n)$ 時間かかる.

11

12

$Q$

ノード

10

end
else
if $flagarrow 1$ thenをノードに分類;
else
ノ $-$ ト作成処理;
end

20

スタヅクから $num(e)$ を取り

13

14$1S$

16

17
18$num(\epsilon)$$Q$$P$出す;

end
22
end
a$
end
24 end21

図 11: マージ関係を表す木から $Q$ ノードの区間を取り出す;
取り出した区問をに分類;$flagarrow 1$ ;

$n$

$n$

$7c\mathfrak{l}ltop(S)$$Q$$\hat{Q}$$T_{m}$

while
do$(e)=L$
if kindthen
Push $(S, num(e))$ :else
if top $(S)\neq num(e)$がノードに分類 then
$Q$

$Q$

$\hat{Q}_{i}$$\hat{Q}_{1}$$\epsilonarrow head(LLoderCI[i])$ ;9942

親子関係の構築アルゴリズム

親子関係の構築アルゴリズムをアルゴリズム 2に示す. アルゴリズム 2 は左端点優先の長さ順序のコンパクトな区間表現 LLorderCI と区間の眉するノードへの分類アルゴリズムで求めた配列
Lam.inarA から $MP\Phi trae$ を構成する.のすべてのノード $N$ は次のようなデータを持つ.

図 13: $Q$ ノードのデータ構造$MP\not\in trae$

1. ノードの種類 kind $(N)$
2. ノードの番号 $num(N)$

ル付けされるノードを地とする. NN』のフラグ$(\hat{P})$ノ $-$$\hat{Q}$$x$$(\hat{P})$$\hat{P}$

ノード

$S$

$P$

特に, リストの先頭はhead $(Child(\hat{P}))$ と表す.

$(S_{i})$のデータ構造は図 13 になる.
アルゴリズム 2 はスタヅク $S$ を用いて親子関係を築く.にはノードの種類と香号の組を格納す
る. 左の端点 $(x, L)$ を読み込んだとき,がラペ$Q$

3. 親へのポインタ Parent $(N)$ノート 戸は上に加えて次のデータを持つ.
1. (間の集合 set
2. 子へのポインタのリスト Child$P$

4. 端点の集合 setの末子でが立っているかを調べる. フラグが立っているとき,は $S$ に格納されており, フラグが立っていないとき,は $S$ に格納されていない. フラグが立っているとき,は $S$ の先頭のノードにラベル付けされる. フラグが立っていないとき,は $S$ の先頭のノードの子になり,を $S$ に格納する. フラグが立っているときの例を図 14 に示し, フラグが立っていない例を図 15 に示す.
右の端点 $(x, R)$ が読み込まれたとする. このとき, ノードが完全であるとき, POP $(S)$ を行う. ノードが完全ではないとき, 何もしない.
以上のように, 各ノードの親子関係を構築する.
$N_{x}$$N_{x}$

トを図示すると図 12 のようになる.

$x$$N_{x}$$N_{x}$$N_{x}$$N_{x}$

図 12: $P$ ノード$Q$

ノード$\hat{Q}$$\hat{P}$のデータ構造のデータ構造について説明する.

$\hat{Q}$で構成されており, それぞれのセクションが子を持つ. $Q$ ノードの末子はセクション$S_{1},$ $S_{2},$$\ldots,$$O^{P_{*}}$$S_{k}$とつながっているセクションを末子セクションという. 図で表すと, 末子セクションは一番右に存在するセクションである.
$S_{k}$とする.

$\hat{Q}$は$S_{k}$$\hat{Q}$の末子セクションをへのポインタ$s\epsilon ction(\hat{Q})$を

図 14: フラグが立っているときの例

持つ.
セクション $S$; は次のようなデータを持っ.

1. ノードへのポインタ $nde(S_{i})$2. 子へのポインタ hild (Si)
3. 両隣りのセクションへのポインタの右隣りのセクション:riht$\ovalbox{\tt\small REJECT}^{P_{i}}$

$Q$

$c$

$s_{:}$$S_{i}$の左隣りのセクション:$(S_{i})$$l\epsilon fl(S_{i})$図 15: フラグが立っていないときの例

100
512$\theta$

4$\tau$今後の課題は本質的に異なるコンパクトな区間表現の列挙が考えられる. また本論文で提案した

for $i=1$ to maxCI do

参考文献$earrow head(LLoderCI[i])$ ;$N_{x}arrow Lam.inarA[num.(\epsilon)]$に端点$e$を書き込む;

2004.

if ki.nd $(e)=L$ thenのフラグ $=0$ thenif
$N_{x}$$N_{x}$PUSH $(S,N_{x})$ :endのフラグを 1 増加;

91011$N_{x}$

$e$

化e13

$\ovalbox{\tt\small REJECT}$のフラグを 1 減少;のフラグ $=0$ then

14

if

15

POP $(S)|$end

16$N_{x}$

20

end
end
if kind $(N_{x})=Q$ thenif $s\epsilon t(Seclion(N_{x}))$ が空 then21

セクション $s_{\epsilon c}u_{on(N_{x})}$ と

22$lefl(Section(N_{x}))$ を結合;
endに新しくセクションを作成;

lf18
19

23

$\ovalbox{\tt\small REJECT}$end
2$ end24を実験的に示す.

$o\eta$;

スタヅクの先頭の子に作成;

アルゴリズムを実装して, 実際に高速であること[1] M. C. Golumbic. Algorithmic Graph Theand Perfect Graphs. ANNALS OF DISCRETE MATHEMATICS 57. ELSEVIER,

while $e\neq NIL$ do

812

区間表現を入力として与えたとき, その区聞表
現に対応する $MP\phi tree$ を構成する場合分けの少ない, かっ高速なアルゴリズムを提案した.

Algorithm 2: 親子開係の構築アルゴリズム
Input: 左端点優先の長さ順序のコンパクトな区間表現 LLorderCI. 眉するノードと種類を表す配列 LaminarA
Output: 射応する $MP\not\in tree$$N_{x}$

6

おわりにを[2] N. Korte and R. H. M\"ohring. An incremental linear-time algorithm for recognizing interval graphs. SIAM Joumal on Computing, $18(1):68-81$ , 1989.
[3] R. Uehara. Canonical Data Structure forInterval Probe Graphs. Lecture Notes in
Computer Science Vol. 3341, pp. $85\succ 870$ ,2004.
[4] K. S. Booth and G. S. Lueker testing for
the Consecutive Ones Property, Interval
Graph8, and Graph Planarity Using P\leq トTbee Algorithms. Joumal of Compter andSystem Sciences, 13, 335-379.
[5] G. S. Lueker and K. S. Booth A Linear Time Algorithm for Deciding Interval
Graph Isomorphism. Joumal of the Association for Computing $Machine\eta$, vol. 26,No.2, pp. $18\succ 195$ , 1979.