Loading article…
グラフ理論において、部分k木はグラフの一種であり、 k木のサブグラフ、または木幅が最大で kであるグラフとして定義されます。[1]グラフ上の多くのNP 困難な組合せ問題は、 kの値が制限されている 場合、部分k木に制限すると多項式時間で解くことができます。
グラフマイナー
任意の固定定数kに対して、部分k木はグラフマイナーの操作によって閉じているため、ロバートソン・シーモア定理により、この族は禁制マイナーの有限集合によって特徴付けることができます。部分 1 木はまさに森であり、その唯一の禁制マイナーは三角形です。部分 2 木の場合、唯一の禁制マイナーは4 頂点の完全グラフです。ただし、 kの値が大きいほど禁制マイナーの数は増加します。部分 3 木の場合、禁制マイナーは 5 頂点の完全グラフ、 6 頂点の八面体グラフ、8 頂点のワグナーグラフ、 10 頂点の五角柱の 4 つです。[2]
動的プログラミング
任意のグラフに対してNP完全である多くのアルゴリズム問題は、これらのグラフの木分解を用いた動的計画法によって部分k木に対して効率的に解くことができる。[3]
関連するグラフのファミリー
グラフ族が木幅に制限がある場合、それは部分k木のサブ族です。ここで、k は木幅の制限です。この特性を持つグラフ族には、サボテングラフ、疑似フォレスト、直列並列グラフ、外平面グラフ、ハリングラフ、アポロニアンネットワークなどがあります。[2]たとえば、直列並列グラフは部分 2 木のサブ族であり、より強い意味では、グラフが部分 2 木であるためには、その2 連結成分のそれぞれが直列並列である必要があります。
構造化プログラムのコンパイル時に生じる制御フローグラフにも制限されたツリー幅があり、これによりレジスタ割り当てなどの特定のタスクを効率的に実行できます。[4]
注記
- ^ ボドランダー（1988年）。
- ^ Bodlaender (1998)より。
- ^ アーンボーグとプロスクロウスキー (1989);ベルン、ローラー、ウォン (1987)。ボードレンダー (1988)。
- ^ ソールプ（1998年）。
参考文献
- Arnborg, S.; Proskurowski, A. (1989)、「部分k木に限定された NP 困難問題に対する線形時間アルゴリズム」、離散応用数学、23 (1): 11–24、doi : 10.1016/0166-218X(89)90031-0。
- Bern, MW; Lawler, EL ; Wong, AL (1987)、「分解可能グラフの最適サブグラフの線形時間計算」、Journal of Algorithms、8 (2): 216–235、doi :10.1016/0196-6774(87)90039-3。
- Bodlaender, Hans L. (1988)、「木幅が制限されたグラフの動的プログラミング」、Proc. 15th International Colloquium on Automata, Languages and Programming、Lecture Notes in Computer Science、vol. 317、Springer-Verlag、pp. 105–118、doi :10.1007/3-540-19488-6_110、hdl : 1874/16258、ISBN 978-3-540-19488-0。
- Bodlaender, Hans L. (1998)、「木幅が制限されたグラフの部分kアーボレタム」、理論計算機科学、209 (1–2): 1–45、doi :10.1016/S0304-3975(97)00228-4、hdl : 1874/18312。
- Thorup, Mikkel (1998)、「すべての構造化プログラムはツリー幅が小さく、レジスタ割り当てが適切である」、Information and Computation、142 (2): 159–181、doi : 10.1006/inco.1997.2697。