非交差最小木の計算複雑度のパラメタ依存について

概要

論文の詳細を見る
平面上に辺を曲線として描画されたグラフ(トポロジカルグラフ)において、辺が交差しない全域部分木を計算する問題を考える。非交差な全域部分木を持つかどうかの判定はNP困難問題であり、交差数を最小化する問題は近似困難である事が知られている。本論文では、以下のような自然なパラメタに対し、パラメトリック計算量(パラメタへの依存度を考慮する計算量)を考察する。対象とするパラメタは、入力されるトポロジカルグラフにおける交差辺対の数k、交差辺の数μ、頂点集合の凸包の内点である頂点数ιである。まず、シンプルなバックトラック探索における改良された戦略を与え、O^*(1.93^k)時間の計算量を与える。これは理論的には大きな改善ではないが、バックトラック探索における実装のガイドラインを与えるという価値を持つ。次に、グラフのセパレータを用いたより洗練されたアルゴリズムにより計算量を改善する。アルゴリズムの計算量はそれぞれのパラメタに対し、O^*(2^<O√<k>>), O^*(μ^<O(μ^<2/3>)>), O^*(ι^<O(√<ι>)>)となる。また、3-SAT問題への帰着により、この問題に対してO^*(2^<√<k>>)の計算量を改善するのは3-SATに対する広く信じられている計算量の仮定の下では困難である事を示す。
2007-05-18

非交差最小木の計算複雑度のパラメタ依存について

スポンサーリンク

概要

著者

関連論文

スポンサーリンク