辞書式順序最小の極大独立点集合を求める問題の並列性の測定
スポンサーリンク
概要
- 論文の詳細を見る
無向グラフの最大有向木サイズ(MDTS)とは、与えられた無向グラフからある手順によって構成される有向グラフ上の有向木の頂点数の最大値によって定義される。MDTSを用いれば、辞書式順序最小の極大部分グラフを求める問題(LFMS問題)の並列性を「測定」することができる。つまり、グラフ族G上でのこの問題の困難さは、MDTSの値につれて以下のように増加していく:(1)Gの各グラフのMDTSの値がある定数κに対して0(log^κn)であるとき、辞書式順序最小の極大独立点集合を求める問題はNC^<κ+1>に属し、グラフ上の性質πに関するLFMS問題はNC^<κ+s>に属する。ただしここでπは、自明でなく、遺伝的で、NC^<s-1>で判断できるものとする。(2)これらの問題は、各グラフのMDTSを高々cn^εに制限したとしてもP完全問題である。ただしc,εは任意の正定数とする。一方任意のグラフ族についてMDTSを計算する問題はNC^2に属する。これは「問題の困難さを測定する」ことは「問題を解く」ことよりも簡単でなくては意味がない、という点で重要である。
- 社団法人情報処理学会の論文
- 1997-03-14
著者
関連論文
- 部分ゲートとその同定
- 多くの計算路によって特徴付られる計算量クラス
- 極大パス集合に対する効率的な並列アルゴリズムとその応用
- Fast $RNC$ and $NC$ Algorithms for Maximal Path Sets and Applications to Superstrings with Flipping
- 制限つきのグラフ上で辞書式順序最小の極大部分グラフを求める問題の並列計算の複雑さ
- 辞書式順序最小の極大独立点集合を求める問題の並列性の測定
- 岩田茂樹著 "NP完全問題入門"
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析