極大パス集合に対する効率的な並列アルゴリズムとその応用
スポンサーリンク
概要
- 論文の詳細を見る
与えられた無向グラフに対して、極大パス集合を求める並列アルゴリズムを2つ構成した。1つめは実行時間の期待値がO(log n)時間のランダムアルゴリズムで、これはCRCW PRAMで、プロセッサ数はO(n+m)個である。2つめは実行時間がO(log^2 n)時間の決定性アルゴリズムで、これはEREW PRAMで、プロセッサ数はO(Δ^2(n+m)/log n)である。ここでnは頂点数、mは辺の数、Δは最大次数である。これらの結果は既知の結果を改善し、また有効グラフ上のアルゴリズムに拡張することができる。次にこの結果を利用してJiangらによって導入されたshortest superstring problem のあるバリエーションに対するNC近似アルゴリズムを構成した。このアルゴリズムは任意のε>0に対して1/(3+ε)の圧縮率を達成する。
- 社団法人情報処理学会の論文
- 1996-05-29
著者
-
上原 隆平
東京女子大学情報処理センター
-
上原 隆平
東京女子大学
-
陳 致中
東京電機大学
-
Xin He
State University of New York at Buffalo
-
陳 致中
東京電機大学理工学部数理科学科
関連論文
- 部分ゲートとその同定
- 多くの計算路によって特徴付られる計算量クラス
- 極大パス集合に対する効率的な並列アルゴリズムとその応用
- Fast $RNC$ and $NC$ Algorithms for Maximal Path Sets and Applications to Superstrings with Flipping
- 制限つきのグラフ上で辞書式順序最小の極大部分グラフを求める問題の並列計算の複雑さ
- 辞書式順序最小の極大独立点集合を求める問題の並列性の測定
- 岩田茂樹著 "NP完全問題入門"
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- Computing Phylogenetic Roots with Bounded Degrees and Errors is Hard (Evolutionary Advancement in Fundamental Theories of Computer Science)
- An Improved Randomized Approximation Algorithm for Max TSP (Theoretical Computer Science and its Applications)
- Improved Deterministic Approximation Algorithms for Max TSP (Theoretical Computer Science and its Applications)
- A Linear-Time Algorithm for 7-coloring 1-planar Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- マップグラフ上の最大点独立集合問題の近似アルゴリズム
- Simple algorithm for recognizing lake-free 4-map graphs (Models of Computation and Algorithms)
- Common-face embeddings of planar graphs with applications (Models of Computation and Algorithms)
- 平面グフフの共通面埋め込み問題とその応用
- 湖なしの4-マップグラフを認識する簡潔なアルゴリズム
- トポロジカル推論について
- 平面マップグラフ
- 完全2部有向グラフ上の最短路問題とその応用
- 重みなし連結度問題に対する効率的近似アルゴリズム
- K_-freeまたはK_5-freeグラフ上の最大化問題に対する実際的なPTAS
- 疎なグラフ上の最大点導出部分グラフ問題のNC近似アルゴリズム
- 平面グラフを森に分割するNCアルゴリズム
- Finding Maximal Cycle-Free Sets in Parallel
- 平面グラフ上の極大f-依存点集合問題がNCに入る
- 極大無閉路集合を求める並列アルゴリズム
- Planar Topological Inference (Algorithms and Theory of Computing)