グラフ論的手法を用いた{2, 3}-EC-SNDPに対する近似アルゴリズム(アルゴリズム, <小特集>ユビキタス社会構築のためのネットワークに対する理論とその応用論文)
スポンサーリンク
概要
- 論文の詳細を見る
辺連結サバイバルネットワーク設計問題(Edge Connectivity Survivable Network Design Problem, EC-SNDP)とは, 無向グラフG=(V, E)と各頂点ペア(u, υ)に対する辺連結要求r_<uυ>が入力として与えられたとき, 各頂点ペア(u, υ)の辺連結度がr_<uυ>以上となるような最小重み部分グラフを出力する問題である. 本研究では, すべての頂点ペア(u, υ)に対する辺連結度r_<uυ>を2または3に制限した, 辺に重みのない{2, 3}-EC-SNDPに対し, 深さ優先探索と極大森を組み合わせたアルゴリズムを提案し, その近似比率が7/3となることを示す. 更に, このアルゴリズムを改良し近似比率が2となることを示す.
- 社団法人電子情報通信学会の論文
- 2005-11-01
著者
-
平田 富夫
名古屋大学大学院工学研究科
-
平田 富夫
名古屋大学大学院情報科学研究科
-
小野 孝男
名古屋大学大学院情報科学研究科
-
勝谷 裕樹
名古屋大学情報科学研究科
-
勝谷 裕樹
名古屋大学情報科学研究科:(現)松下電工株式会社
-
平田 富夫
名古屋大学
関連論文
- 直接計算による楕円曲線上のスカラ倍計算の効率化(情報セキュリティ基礎)
- モンゴメリのトリックを用いた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部グラフ上のハミルトン閉路アルゴリズム (アルゴリズムと計算理論の新展開)
- たて糸張力均一条件下における綜絖枠数最小化
- たて糸張力均一条件下における綜絖枠数最小化
- 張力均一条件下におけるドビー織機の綜絖枠数最小化