数理解析研究所講究録
第 1649 巻 2009 年 145-152

145

正則グラフのデカルト冪に対するカービング幅
群馬大学大学院工学研究科 小澤恭平 (Kyohei Kozawa),
大舘陽太 (Yota Otachi), 山崎浩一 (Koichi Yamazaki)
Department of Computer Science,
Gunma University

1

はじめにグラフのカービング幅の概念は, Seymour と Thomas [8] によって導入された. 彼らはその中で. 一般のグラフに対するカービング幅を決定する問題は NP 困難であること, 一方で,頂点の平面グラフに対しては $O(n^{4})$ 時間で解けることを示した. その後, Gu と Tamaki[5] は, Seymour
等の平面グラフに対する $O(n^{4})$ 時間のアルゴリズムを $O(n^{3})$ に改善した. また, Thilikos 等 [9]$n$$\}$

は,近,グラフのカービング幅を決定する問題に対して, 構成的に固定パラメータ容易性を示した. 最Chandran と Kavitha [2] が, カービング幅と境界辺問題の関係を示し, それを用いて 次元$d$

ハイパーキューブのカービング幅がであることを示した.
本論文では, カービング幅と境界辺問題の関係と, Bezrukov と Els\"asser [1] が示した, 正則グラ
$2^{d-1}$フのデカルト幕に対する境界辺問題の結果を用いて, 正則グラフのデカルト幕に対するカービング幅の下界を示す. この結果は, Chandran と Kavitha[2] によるハイパーキューブのカービング幅,
Furuse 等 [3] によるハミンググラフのカービング幅, それぞれの下界に対する自然な拡張である.

2 準備
この節では, まず, カービング幅と関係のある境界辺問題を定義する. 次に, グラフのカービング幅を定義する. 最後に, 本論文で主に扱うグラフである正則グラフのデカルト幕を定義する.

2.1 境界辺集合
グラフ $G$ の部分頂点集合 $U,$ $W\subseteq V(G)$ に対して, $E(U, W)=\{\{u,w\}\in E(G)|u\in U,w\in$$W\}$ とする.
グラフ $G$ の部分頂点集合 $S\subseteq V(G)$ に対して, $S$ と $V(G)-S$ の間にある辺の集合
を,$S$の境界辺集合といい,と表記する. すなわち,$\theta c(S)$$\theta_{G}(S)=\{\{u,v\}\in E(G)|u\in S,v\in$$V(G)-S\}$ である. ただし, 扱うグラフが文脈から明らかな場合, グラフを表す添字を省略する.

整数 $1\leq s\leq|V(G)|$ に対して. この関数$\theta(s)=\min_{S\subseteq V(G),|S|=\theta}|\theta(S)|$$\theta$を, 次のように.

以上の定義より, 次の主張が成り立つ.
主張 2.1. $\theta(S)=\theta(V(G)-S),$ $\theta(s)=\theta(|V(G)|-s)$ .

$s$の関数に拡張する :146

グラフ $G$ において,$|\theta(S_{\epsilon})|=\theta(s)$$1\leq s\leq|V(G)|$ に対して,かつ $|S_{e}|=s$ となるような頂点集合

このような$S_{s}$

グラフ $G$ が, 以下を満たすような列をグラフ $G$ は, 境界辺問題に対して入れ子構造を持つという :持つとき,$S_{1}\subset S_{2}\subset\cdots\subset S_{|V(G)|}$$P_{4}\cross P_{4}$.

は, 境界辺問題に対して入れ子構造を持つが, $P_{5}xP_{5}$ は, 境界辺問題に対して入れ子構造を持たない (22について考える. 各を求める問題を境界辺問題という. 一般のグラフに対して, 境界辺問題が NP 困難であることが知られている [4].

例えば,

$S_{\delta}$$\cross$は,グラフのデカルト積を表す演算子であり, この後の小節で定義する).

カービング幅

カービングは, クロスという集合同士の関係を用いて定義することもできるし,(全ての内点の次数が 3 である木) を用いて定義することもできる.

ターナリー木

ここではクロスを用いた定義のみを紹介する (木による定義は文献 [8] 参照).
$\blacksquare$

二つの部分集合 $A,$ $B\subseteq V$ に対して,クロスという集合同士の関係を用いたカービングの定義$A\cap B,$$V$..
.

$A-B,$ $B-A,$ $V(G)-(A\cap B)$ のいずれも空集合でないとき, $A$ と $B$ がクロスするという.のカービングとは, 以下を満たす $V$ の部分集合族曽である.
$\emptyset,$$V\not\in\varphi$,

望のどの二つの部分集合もクロスしない,$\wp$

は, 上の二つの条件を満たし,極大である.

グラフ $G$ の頂点集合 $V(G)$ に対するカービング望の幅を,及び表記する. グラフ $G$ のカービング幅を,width $( \wp)=\max s\in w|\theta(S)|$ と定義,$V(G)$ の全てのカービングの,最小の幅と定義し,と表記する.

$cw(G)$

23 正則グラフのデカルト幕
まず,$d$次元デカルト幕を定義する. グラフ $G$ と $H$ に対して,は, 頂点集合が $V(G\cross H)=V(G)\cross V(H)$ で,$G\cross H$$G$と $H$ のデカルト積 $G\cross H$ との 2 頂点 $(g, h)$ と $(g’, h’)$ が隣接する必要十分条件が, 次のとおりのグラフである :$\bullet$$\bullet$$g=g^{/}$ かつ$\{h,$$h^{/}\}\in E(H)$ ,または, $h=h’$ かつ $\{g,g’\}\in E(G)$ .

デカルト積の演算には, 交換法則と結合法則が成り立つ.
グラフ $G$ の$d$次元デカルト幕を, 以下によって定義し.

$G^{d}=\{\begin{array}{ll}G d=1,GxG^{d-1} d\geq 2.\end{array}$$G^{d}$と表記する :

147

図1

$K_{8}$から 2 個の互いに素な完全マッチングを削除することで得られる$H_{4,2}$次に, 証明に用いる, 特別な正則グラフ H 函を定義する. 頂点数 $2p$ の完全グラフ $K_{2p}$ の頂点集合を $\{0,1, \ldots, 2p-1\}$ とする. この頂点集合を, $U=\{0,1, \ldots,p-1\},$ $W=\{p,p+1, \ldots, 2p-1\}$と二つに分割する. 正則グラフ$i$個の互いに素な$U,$$W$$H_{p,i}$とは, 頂点集合が $V(K_{2p})$ と等しく, 辺集合が $E(K_{2p})$ から間の完全マッチングを削除したグラフである. 図 1 は,

$K_{8}$から 2 個の互いに素な完全マッチングを削除することで得られるである. ここで, 完全マッチングの選び方により得られる正則グラフは, 非同型となることもある. しかし, 関数 のとる値は変わらない$H_{4,2}$$\theta$

完全マッチングの選び方は気にしなくてよい.
Bezrukov と Elsasser 1 は, 境界辺問題での正則グラフのデカルト幕とため,$[$$]$$H_{p,i}^{d}$の関係を示した.

補題 2.2 (Bezrukov と Elsasser [1]). あるグラフ $G$ が次の条件を満たすとする.

.

$\bullet$$\bullet$

境界辺問題に対して入れ子構造を持つ,$|V(G)|=2p$ ,$2p-i-1$ 正則である.

このとき, 任意の $d\geq 1$ と $1\leq s\leq(2p)^{d}$ に対して, 以下の関係を満たす.
$\theta_{H_{p,i}^{d}}(s)\leq\theta_{G^{d}}(s)$.

ハイパーキューブやハミンググラフなどの正則グラフのデカルト幕で表現されるグラフクラスに対して, 境界辺問題は盛んに研究されている [6, 7]. Bezrukov とEls\"asser[1] は, 特別な正則グラ
フ$H_{p,i}^{d}$のデカルト幕に対する境界辺問題を, 辞書式順序を用いて解いた.

補題 2.3 (Bezrukov と Els 温 8Ser [1]). 任意の $1\leq s\leq|H_{p,i}^{d}|,$ $0\leq i\leq p/2$ に対して, 辞書式順序での最初の 頂点を $S$ とする. このとき, $\theta(s)=|\theta(S)|$ である.
$H_{p,i}^{d}$$s$

3 正則グラフのデカルト幕に対するカービング幅の下界
Chandran と Kavitha [2] は, カービング幅と境界辺問題に次の関係があることを示した.
補題 3.1 (Chandran と Kavitha [2]). $G$ をグラフとし,の関係を満たす.
$\min$$cw(G) \geq_{1}\max_{\leq x\leq|V(G)|x/2\leq\epsilon\leq x}$$\theta(s)$.

$1\leq X\leq|V(G)|$ とする.

このとき, 以下148

Chandran と Kavitha はこの関係を用いて, ハイパーキューブ$K_{2}^{d}=P_{2}^{d}$に対してカービング幅を示した [2].

補題 31 の変数
系 32. 頂点数$n$$x$を $2|V(G)|/3$ に固定し, 主張 21 で示した対称性から, 次の系が導ける.の任意のグラフ $G$ に対して,$cw(G) \geq\min_{\lceil n/3\rceil\leq\epsilon\leq\lfloor n/2\rfloor}\theta(s)$.

準備がととのったので, 正則グラフのデカルト幕に対するカービング幅の下界を示す.

.

定理 3.3. $p\geq 3,0\leq i\leq p/2,$ $d\geq 2$ とする. あるグラフ $G$ が次の条件を満たすとする.

境界辺問題に対して入れ子構造を持つ,$\bullet|V(G)|=2p$ ,$\bullet$$2p-i-1$ 正則である.

このとき,$cw(G^{d})\geq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{a}p\rfloor-i) 0\leq i<\lfloor p/3\rfloor,p(2p)^{d-1}(p-i) |p/3\rfloor\leq i\leq\lfloor p/2\rfloor.\end{array}$証明. 本定理を示すには. 補題 22 と系 32 より,$\lceil(2p)^{d}/3\rceil\leq s\leq\lfloor(2p)^{d}/2\rfloor$に対して以下を示

せばよい.

(1)

$\theta(s)\geq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i) 0\leq i<\lfloor p/3\rfloor,p(2p)^{d-1}(p-i) \lfloor p/3\rfloor\leq i\leq[p/2\rfloor.\end{array}$

任意の整数 $\lceil(2p)^{d}/3|\leq s\leq\lfloor(2p)^{d}/2\rfloor$ に対して, 部分集合 $S\subseteq V(H_{p,i}^{d})$ を, 辞書式順序で$H_{p,i}^{d}$の最初の$s$頂点とする. このとき. 補題 23 より,$|\theta(S)|=\theta(s)$である. 正整数$q$と$r$を,$s$を $(2p)^{d-1}$ で除算したときの商と余りとする. すなわち, $s=q(2p)^{d-1}+r$ である. また, このとき.

$\lfloor 2p/3\rfloor\leq q\leq p$である.

集合 $S’$ を, 辞書式順序で後の$r$の最初の $(q+1)(2p)^{d-1}$ 頂点, 集合 $R$ を. 辞書式順序で $S$ の最$H_{p,i}^{d}$

頂点, 集合 $T$ を, $S’-S$ とする (図 2 参照).

ここで, $|R|=r,$ $|T|=(2p)^{d-1}-r$ であることに注意する.

以上の定義より. 次の五つの主張が成り立つことは容易に確認できる.
主張 3.4. $|E(S, V(G)-S’)|=(2p-i-1-q)|S|$ .

主張 3.5. $|E(T, S-R)|=q|T|$.

主張 S.6.

$|E(T,\overline{S’})|=(2p-i-1-q)|T|$

主張 3.7.

$|T|\leq(2p)^{darrow 1}/2$.のとき, $|E(T, R)|\geq|T|(p-i)$.

主張 3.8. $|T|>(2p)^{d-1}/2$ のとき, $|E(T, R)|\geq|T|(q-i)$ .

149

この後,の値により,のケースと,のケースの二つに分けて考えていく. ここで, $p\equiv 0(mod 3)$ のとき, $\lfloor 2p/3\rfloor\leq q<\lceil 2p/3\rceil$ の範囲には, 整数は存在しない$q$$q\geq\lceil 2p/3\rceil$

ので, 必ず $q\geq\lceil 2p/3\rceil$ のケースになる.の範囲には, 整数は1.
2.
$\blacksquare$$q\geq\lceil 2p/3\rceil$$q=\lfloor 2p/3\rfloor$

ケース 1$\lfloor 2p/3\rfloor$

また,$\lfloor 2p/3\rfloor\leq q<\lceil 2p/3\rceil$$p\not\equiv O(mod 3)$のときでも,$\lfloor 2p/3\rfloor\leq q<\lceil 2p/3\rceil$しか存在しない. よって, 以下のケース分けによって考えていく.

,
かっ $p\not\equiv 0(mod 3)$$q\geq\lceil 2p/3\rceil$.

: $|\theta(S)|\geq|E(S, \overline{S’})|+|E(T, S-R)|$ であり, 主張 3.4 と主張 35 より,$|\theta(S)|\geq(2p-i-1-q)(q(2p)^{d-1}+r)+q((2p)^{d-1}-r)$$=q(2p)^{d-1}(2p-i-q)+r(2p-i-1-2q)$ .
式 (2) の第二項が.

$0$以上となる必要十分条件を主張 39. 式 (2) の第二項, $r(2p-i-1-2q)$ が$0$$q$(2)と $r$ の値によって示す.

以上となる必要 $+$ 分条件は,$\lceil\frac{2}{3}p]\leq q\leq p-22-\frac{1}{2}$または, $r=0$ のどちらかを満たすことである.

主張 39 より,$|\theta(S)|\geq\{\begin{array}{ll}q(2p)^{d-1}(2p-i-q) \lceil\frac{2}{3}p\rceil\leq q\leq p-\frac{i}{2}-\frac{1}{2} \text{または} r=0,q(2p)^{d-1}(2p-i-q)+r(2p-i-1-2q) p_{\vec{2}}^{i}--\frac{1}{2}<q\leq p-1 \text{かつ} r\neq 0.\end{array}$

以降,

A.

$q$と$r$の値により, 更に二つのケースに分けて式 (1) の関係を示していく.

$\lceil\frac{2}{3}p|\leq q\leq p-\frac{i}{2}-\frac{1}{2}$または $r=0$ ,B. $p- \frac{:}{2}-\frac{1}{2}<q\leq p-1$ かつ $r\neq 0$ .
ロケース 1-A$\lceil\frac{2}{3}p\rceil\leq q\leq p-\frac{i}{2}-\frac{1}{2}$または $r=0:f_{A}(q)=q(2p)^{d-1}(2p-i-q)$ とする.

二次関数 $f_{A}(q)$ は, 上に凸なので, 区間$[ \lceil\frac{2}{3}p\rceil,p]$に対する $f_{A}(q)$ の最小値は,のどちらかである.
以上より, ケース 1-A における本定理を証明するには. 以下を示せばよい.

$f_{A}( \lceil\frac{2}{3}p\rceil)$

このか $f_{A}(p)$150(1-A-a)$f_{A}( \lceil\frac{2}{3}p])\geq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i) 0\leq i<\lfloor p/3\rfloor,p(2p)^{d-1}(p-i) \lfloor p/3\rfloor\leq i\leq\lfloor p/2\rfloor,\end{array}$(1-A-b)$f_{A}(p)\geq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i) 0\leq i<\lfloor p/3\rfloor,p(2p)^{d-1}(p-i) \lfloor p/3\rfloor\leq i\leq\lfloor p/2\rfloor.\end{array}$

式 (1-Aa) の関係であるから,$f_{A}( \lceil\frac{2}{3}p\rceil)=\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i)$$\lfloor p/3\rfloor\leq i\leq|p/2\rfloor$に対して,(3)$\lceil\frac{2}{3}p](2p)^{darrow 1}(\lfloor\frac{4}{3}p\rfloor-i)\geq p(2p)^{d-1}(p-i)$を示せばよい. 式 (3) を$i$について解くことで, 式 (3) の関係を満たす$i$の範囲を求める.

$\lceil\frac{2}{3}p](2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i)\geq p(2p)^{d-1}(p-i)$$(p- \lfloor\frac{p}{3}\rfloor)(p+\lfloor\frac{p}{3}\rfloor-i)\geq p(p-i)$$p^{2}-( \lfloor\frac{p}{3}\rfloor)^{2}-(p-\lfloor\frac{p}{3}\rfloor)i\geq p^{2}-\dot{\mu}$$i \geq\lfloor\frac{p}{3}\rfloor$.

よって, 式 (1-A-a) の関係は成り立つ.

式 1-A-b の関係
$)$

$($

$f_{A}(p)=p(2p)^{d-1}(p-i)$ であるから,$0\leq i<\lfloor p/3\rfloor$に対して,$p(2p)^{d-1}(p-i) \geq\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i)$を示せばよい. これは, 式 (3) の対偶より,$i<\lfloor$引のとき満たすことが分かる. よって, 式(1-A-b) の関係は成り立つ.
ロケース 1-Bる.

$p- \frac{i}{2}-\frac{1}{2}<q\leq p-1$

かつ $r\neq 0$ : まず,$q$の範囲より,$i\geq 2$$f_{B}(q)=q(2p)^{d-1}(2p-i-q)+r(2p-i-1-2q)$ とする. この二次関数

ので, 区間である.

$(p- \frac{i}{2}-\frac{1}{2}$, $p-1]$ に対する $f_{B}(q)$ の下界は,$r\leq(2p)^{d-1}/2$$f_{B}(p- \frac{i}{2}-\frac{1}{2})$と $r>(2p)^{d-1}/2$ に分けて考えていくと,であることが分か$f_{B}(q)$は, 上に凸なか $f_{B}(p-1)$ のどちらかどちらの場合も $f_{B}(p-1)$ が下界になることが示せる. よって, ケース 1-B における本定理を証明するには, 以下を示せばよい.

$f_{B}(p-1)\geq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i) 0\leq i<1p/3\rfloor,p(2p)^{d-1}(p-i) \lfloor p/3\rfloor\leq i\leq\lfloor\rho/2\rfloor.\end{array}$

式 (1-B) の関係$f_{B}(p-1)=(p-1)(2p)^{d-1}(p-i+1)-r(i-1)$$=p(2p)^{d-1}(p-i)+(2p)^{d-1}(i-1)-r(i-1)$$\geq p(2p)^{d-1}(p-i)$$(\cdot.\cdot r<(2p)^{d-1})$

.

(1-B)

151

であるから, あとは,$0\leq i<\lfloor p/3\rfloor$に対して,$p(2p)^{d-1}(p-i) \geq r_{\vec{3}^{p}}^{2}](2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i)$を示せぱよい. この関係は, すでに [式 (1-A-b) の関係」にて示しているので, 式 (1-B) の関係は成り立っ.
ケース 2$q=\lfloor 2p/3\rfloor$$\lceil 2p/3\rceil-1$である. 故に,$\blacksquare$

かつ $P\not\equiv 0(mod 3):_{P}$ が 3 の倍数でないことから,$|S’|=\lceil 2p/3\rceil(2p)^{d-1}$$q=\lfloor 2p/3\rfloor=$であり, ケース 1 で示したように, 以下の関係を満たす.

$|\theta(S’)|\geq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{darrow 1}(\lfloor\frac{4}{\theta}p\rfloor-i) 0\leq i<\lfloor p/3\rfloor,p(2p)^{d-1}(p-i) \lfloor p/3\rfloor\leq i\leq\lfloor\rho/2\rfloor.\end{array}$

よって,$|\theta(S)|\geq|\theta(S’)|$を示せば十分である.

この $S’$ の境界辺集合の大きさを,$S$の境界辺集合の大きさとの差分を用いて表すと以下のようになる (図 2 参照).
$|\theta(S’)|=|\theta(S)|-|E(T, R)|-|E(T, S-R)|+|E(T, \overline{S’})|$.

主張 35 と主張 36 より,$|\theta(S’)|=|\theta(S)|-|E(T_{f}R)|+|T|(2p-i-1-2q)$

この後,となる.

$|T|$の大きさによって, 二つのケースに分けて考える.

A. $|T|\leq(2p)^{d-1}/2$ ,B. $|T|>(2p)^{d-1}/2$ .
ロケース 2-A$|T|\leq(2p)^{d-1}/2$: 主張 37 より,$|\theta(S’)|\leq|\theta(S)|+|T|(p-1-2q)\leq|\theta(S)|$ロケース 2-B$\frac{2}{3}(2p)^{d-1}$.

$|T|>(2p)^{d-1}/2:p\equiv 1(mod 3)$ ならば,$\underline{2}_{R,3}=L_{3}^{B}2\rfloor+\frac{2}{3}$であるから,$|R|\geq$である. よって, $|T|=(2p)^{d-1}-|R|<(2p)^{d-1}/2$ となり, このケースは起こり得な $A|$.

したがって, このケースが起こるのは $p\equiv 2(mod 3)$ のときあり, このとき, $3q+1=2p$ である.
主張 38 より,$|\theta(S’)|\leq|\theta(S)|+|T|(2p-(3q+1))=|\theta(S)|$以上で本定理を証明できた.

.
口152

4まとめ
本論文では, ある条件を満たす正則グラフのデカルト幕に対するカービング幅の下界を示した.

..
.

より正確には,$p\geq 3,0\leq i\leq p/2,$$d\geq 2$であり,グラフ $G$ が,境界辺問題に対して入れ子構造を持ち,$|V(G)|=2p$ であり,$2p-i-1$ 正則である

場合の,$G^{d}$のカービング幅に対する以下の下界を示した :$cw(G^{d})\geq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i) 0\leq i<\lfloor p/3\rfloor,p(2p)^{d-1}(p-i) \lfloor p/3\rfloor\leq i\leq\lfloor p/2\rfloor.\end{array}$

また, 本論文では述べていないが. ある特定のマッチングの選び方をした $H_{p,i}$ を$F_{p,i}^{d}$$F_{p,i}$とすると,のカービング幅の上界が,$cw(F_{p,i}^{d})\leq\{\begin{array}{ll}\lceil\frac{2}{3}p\rceil(2p)^{d-1}(\lfloor\frac{4}{3}p\rfloor-i) 0\leq i<\lfloor p/3\rfloor,p(2p)^{d-1}(p-i) [p/3\rfloor\leq i\leq\lfloor p/2\rfloor.\end{array}$であることを構成的に示せる.

したがって, 本論文で示した下界は,これ以上改善できない.

参考文献[1] S. L. Bezrukov and R. Els\"asser. Edge-isoperimetric problems for cartesian powers of regulargraphs. Theor. Comput. Sci., Vol. 307, pp.
, 2003.
[2] L. S. Chandran and T. Kavitha. The carvingwidth of hypercubes. Discrete Math., Vol. 306, pp.
2270-2274, 2006.
[3] M. Furuse, K. Kozawa, Y. Otachi, and K. Yamazaki. The carving-width of generalized hypercubes.
$473\triangleleft 92$

2009. 投稿中.
[4] M. R. Garey and D.S. Johnson. Computers and intractability: A guide to the theory of NPcomp leteness. W. H. Freeman, 1979.
[5] Q.-P. Gu and H. Tamaki. Optimal branch-decomposition of planar graphs in $O(n^{3})$ time. $ACM$
TVans. Algorithms, Vol. 4, . Article No. 30, 2008.
[6] L. H. Harper. Optimal assignments of numbers to vertices. J. Soc. $Ind$ . Appl. Math., Vol. 12, pp.
$p$131-135, 1964.
[7] J. H. Lindsey II. Assignment of numbers to vertices. Amer. Math. Monthly, Vol. 71, pp. 508-516,

1964.
[8] P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, Vol. 14, pp.
217-241, 1994.
[9] D. M. Thilikos, M. J. Sema, and H. L. Bodlaender. Constructive linear time algorithms for small
cutwidth and carving-width. In ISAAC 2000, Vol. 1969 of Lect. Notes. Comput. Sc., pp. 192-203.
Springer-Verlag, 2000.