Triangle-free graphの独立集合問題に対する貪欲アルゴリズムの解析
スポンサーリンク
概要
- 論文の詳細を見る
独立集合問題の入力として頂点数nと平均次数d^^-のグラフが与えられたとき,少なくともn/(d^^-+1)のサイズの近似解を得る貪欲アルゴリズムがある.この値はTuran boundとして知られている.この貪欲アルゴリズムを線形計画法と組み合わせると(J^^-+1)/2の近似率が得られる.本論文では,入力をtriangle-free graphに限定した独立集合問題において,貪欲アルゴリズムによってサイズが少なくとも2n/(d^^-+4)の近似解が得られることを示す.更に,貪欲アルゴリズムと線形計画法を組み合わせると(d^^-+4)/4の近似率が得られることを示す.
- 一般社団法人情報処理学会の論文
- 2008-01-18
著者
関連論文
- 直接計算による楕円曲線上のスカラ倍計算の効率化(情報セキュリティ基礎)
- モンゴメリのトリックを用いた2^kP倍点の改良計算法
- 楕円曲線上のスカラー倍計算の効率化 : ヤコビアン座標系上での直接計算法の提案 (計算機科学基礎理論の新展開)
- 楕円曲線上のスカラー倍点計算法の改良
- D-1-9 集合基底問題の正規基底を求める発見的アルゴリズム(D-1.コンピュテーション,一般セッション)
- 集合基底問題の正規基底を求めるヒューリスティックアルゴリズム
- 詳細配置問題を組み込んだ配線モデル
- 詳細配置問題を組み込んだ配線モデル
- COMP2000-14 ネット割当て問題のヒューリスティック解法に関する研究
- ネット割当て問題に対するヒューリスティックアルゴリズムの評価
- D-1-1 ネット割り当て問題に関する一考察
- ユークリッド距離変換アルゴリズムの効率化
- 効率の良いモルフォロジー演算が可能なフィルタ形状について
- 効率の良いモルフォロジー演算が可能なフィルタ形状について
- 中山間地におけるデマンドバスシステムの開発 : デマンドバスの実際的経路探索法
- 平面配線における配線可能性検証の効率化
- 配線可能性検証のための容量判定グラフとフロー導出グラフ
- 配線可能性検証のための容量判定グラフの提案
- 配線可能性検証のための容量判定グラフの提案
- 多点対カット問題に対する集合被覆アプローチに基づく近似解法
- Triangle-free graphの独立集合問題に対する貪欲アルゴリズムの解析
- LA-004 Analysis of an Edge Coloring Algorithm Using Chernoff Bounds
- Chernoff Bounds を用いた辺彩色アルゴリズムの解析
- 半定値計画法にもとづく彩色問題の発見的解法
- グラフ論的手法を用いた{2, 3}-EC-SNDPに対する近似アルゴリズム(アルゴリズム, ユビキタス社会構築のためのネットワークに対する理論とその応用論文)
- グラフ論的手法を用いた{2, 3}-EC-SNDPに対する近似アルゴリズムの研究
- 重み付き独立集合問題に対する近似アルゴリズム
- 多重グラフの均等辺彩色問題に対するアルゴリズム
- 多重グラフの均等辺彩色問題に対するアルゴリズム
- シストリックアレイによるユークリッド距離変換アルゴリズムの実現
- k-colorableグラフの点彩色問題の近似アルゴリズムに対する議論
- 4-colorableグラフの点彩色問題に対する近似アルゴリズム
- ユークリッド距離変換アルゴリズムのハードウェア化に関する研究
- ドビー織機の綜絖枠数最小化問題に対する集合被覆アプローチ
- ドビー織機における必要綜絖枠枚数の最小化
- 2層配線における発見的ビア数最少化手法
- 2層配線における発見的ビア数最少化手法
- 平面配線可能性検証アルゴリズムの実現 (電子システムの設計技術と設計自動化)
- 配線可能性検証のためのフロー計算アルゴリズム
- 配置処理のための領域分割の改善
- 配置処理のための領域分割の改善
- B-スプライン関数による布の傷の高速検出
- B-スプライン関数による布の傷の高速検出
- LA-005 辺縮約問題の近似困難性(A分野:モデル・アルゴリズム・プログラミング)
- MIN 3-SET COVERの近似困難性
- MIN 3-SET COVER の近似困難性
- 織方図作成における最適化問題のグラフによる定式化 (数値最適化の理論と実際)
- ネット割当てアルゴリズムの改良
- 摂動法によるMAX SAT近似アルゴリズムの改良
- MAX SATに対するハイブリッド法
- 摂動法によるMAX SAT近似アルゴリズムの改良
- Approximation Algorithms for MAX SAT : Semidefinite Programming and Network Flows Approach
- MAX SATに対するYannakakisのアルゴリズムの精密化
- LA-003 ドビー織機における必要綜純粋枚数の最小化(モデル・アルゴリズム・プログラミング)
- 長目綜絖導入による製織可能な織物組織数の増加
- 長目綜絖を用いた場合の織物組織数の増加
- 近似アルゴリズムの実用化
- デマンドバスシステムにおける実際的経路探索法
- 警備員経路アルゴリズムの時間解析について
- MAX SATに対する近似アルゴリズム
- MAX 3-SATに対する高性能近似アルゴリズム
- ユークリッド距離変換アルゴリズム
- [フェロー受賞記念講演]レベルセット法と距離変換アルゴリズム
- たて糸張力均一条件下における綜絖枠数最小化 (コンピュテーション)
- 距離遺伝2部グラフ上のハミルトン閉路アルゴリズム (アルゴリズムと計算理論の新展開)
- たて糸張力均一条件下における綜絖枠数最小化
- たて糸張力均一条件下における綜絖枠数最小化
- 張力均一条件下におけるドビー織機の綜絖枠数最小化