重みなし連結度問題に対する効率的近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿では、二つのNP困難な問題に対する効率的な近似アルゴリズムを提案する。一つ目の問題は次のとおりである: 整数kとk-辺連結グラフG=(V, E)が与えられたとき、グラフ(V, E')がk-辺連結であるような最小サイズのE'⊆E を求めよ。この問題に対して、以下の性質を持ったアルゴリズムを提案する: (1) すべてのkに対して、近似率は1.924である。(2) 逐次的にはO(k(n+m))時間である。これは、近似率が2より小さくかつ時間量がO(k(n+m))である、最初のアルゴリズムである。(3) 並列にはn+m個のプロセッサを用い、O(klog^3 n)時間である。これは、近似率が2より小さくかつ時間量がnの対数多項式である、最初の並列アルゴリズムである。(4) Gが単純グラフでかつk≥0.38nであるとき、近似率は既知のべスト1.85より小さい。二つ目の問題は次のとおりである: 整数kとk-頂点連結グラフG=(V, E)が与えられたとき、グラフ(V, E')がk-頂点連結であるような最小サイズのE'⊆Eを求めよ。この問題に対して、近似率が1.96で線形時間の近似アルゴリズムを提案する。これは近似率が2より小さい最初の多項式時間アルゴリズムである。
- 一般社団法人情報処理学会の論文
- 1996-07-24
著者
関連論文
- 極大パス集合に対する効率的な並列アルゴリズムとその応用
- 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)