極大無閉路集合を求める並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
グラフG=(V,E)のスパニング森(spanning forest)は、次を満たすEの極大な部分集合Fである:Fによって導出されるGの部分グラフが閉路(cycle)を持たない。グラフG=(V,E)の極大無閉路集合は、次を満たすVの極大な部分集合Uである:Uによって導出されるGの部分グラフが閉路を持たない。グラフのスパニング森を求める効率のよい並列アルゴリズムが数多く知られている。しかし、グラフの極大無閉路集合を求める効率のよい並列アルゴリズムがまだ知られていなく、おそらく存在しないだろうと予測されている。本研究では、制限されたグラフの極大無閉路集合を求める効率のよい並列アルゴリズムを示す。得られた結果は次の通りである。平面グラフの極大無閉路集合がO(n)個のプロセッサを用いてO(log^3n)時間で求められる。また、相対的に短いパスしか持たないグラフの極大無閉路集合がO(n^2.376>)個のプロセッサを用いて対数多項式時間で求められる。
- 社団法人電子情報通信学会の論文
- 1993-11-26
著者
-
陳 致中
東京電機大学理工学部数理科学科
-
何 新
ニューヨーク州立大学バファロー
-
陳 致中
Department of Information Engineering,Faculty of Engineering,Mie University
-
何 新
三重大学工学部情報工学科
-
陳 致中
三重大学工学部情報工学科
関連論文
- 極大パス集合に対する効率的な並列アルゴリズムとその応用
- Fast $RNC$ and $NC$ Algorithms for Maximal Path Sets and Applications to Superstrings with Flipping
- 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)
- Practical PTAS for Maximum Induced-Subgraph Problems on $K_{3,3}$-free of $K_5$-free Graphs
- FP^_>||>のある特徴付けと完全問題