2部グラフ描画問題に対する近似アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• 2部グラフ描画における辺交差数最小化問題は,NP困難であることが知られている.本稿では,この問題に対する多項式時間近似アルゴリズムを提案し,その近似精度と入力グラフの最大次数との関係を述べる.最大次数が4以下の場合,本アルゴリズムが出力する解の辺交差数と最適解の辺交差数との比は2以下になり,最大次数が大きくなるにつれてこの値は漸近的に3に近づく.また,計算機実験によって,本アルゴリズムと従来法である重心法やメジアン法とを比較し,頂点数やグラフの最大次数にかかわらず,本アルゴリズムの方が良い解を出力することを示す.

• 一般社団法人情報処理学会の論文
• 1999-10-15

著者

• 山口 敦子

  (株)日立製作所基礎研究所

• 杉本 晃宏

  日立製作所基礎研究所:(現)京都大学大学院情報学研究科

• 杉本 晃宏

  日立製作所

• 山口 敦子

  日立製作所中央研究所

• 山口 敦子

  日立製作所基礎研究所:(現)生物分子工学研究所

• 山口 敦子

  日立製作所 中央研究所

関連論文

• 最小共通包含木問題に対する並列近似アルゴリズム
• 低分子EUVレジストの開発
• 金谷健一(著), 形状CADと図形の数学 工系数学講座19, 共立出版, 1998年, 2500円(税別), ISBN4-320-01618-1
• 2部グラフ描画問題に対する近似アルゴリズム
• 2部グラフ描画に対する近似アルゴリズム
• Cu/low-k配線パターンのラインエッジラフネス評価(配線・実装技術と関連材料技術)
• 2次曲線に基づいて2次元射影変換を求める線形アルゴリズム
• コニック対応に基づく平面物体の画像変換 : 冗長性を利用した線形アルゴリズム
• 物体の見え方によらない情報の抽出 : 幾何学的不変量の画像理解への応用
• 65nmプロセスノードに対応するCD-SEM技術 (特集1 ナノメートル時代の最先端半導体デバイスの量産を支えるベストソリューション)

スポンサーリンク