制限つきのグラフ上で辞書式順序最小の極大部分グラフを求める問題の並列計算の複雑さ

スポンサーリンク

概要

• 論文の詳細を見る

• 最長有向パス長(LDPL)とは与えられた無向グラフから構成される有向で無閉路なグラフ上の有向路の長さの最大値である。与えられたグラフのLDPLは辞書式順序最小の極大部分グラフを求める問題(LFMS)の並列計算の複雑さを『測る』ことができる。つまりLDPLの大きさがO(log^k n)のときはこの問題はNCに属し、一方LDPLがcn^εのときはこの問題はP-完全問題となる。またLDPLを計算する問題自身は、NC^2に属する。ランダムグラフG(n,p)上のLDPL lに関する閾値関数は1/nとなることも示された。

• 社団法人電子情報通信学会の論文
• 1997-11-14

著者

• 上原 隆平

  東京女子大学情報処理センター

• 上原 隆平

  東京女子大学

関連論文

• 部分ゲートとその同定
• 多くの計算路によって特徴付られる計算量クラス
• 極大パス集合に対する効率的な並列アルゴリズムとその応用
• Fast $RNC$ and $NC$ Algorithms for Maximal Path Sets and Applications to Superstrings with Flipping
• 制限つきのグラフ上で辞書式順序最小の極大部分グラフを求める問題の並列計算の複雑さ
• 辞書式順序最小の極大独立点集合を求める問題の並列性の測定
• 岩田茂樹著 "NP完全問題入門"
• 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析

スポンサーリンク