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

元データ 1998-09-16 一般社団法人情報処理学会

概要

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

著者

山口 敦子 (株)日立製作所基礎研究所
杉本 晃宏 日立製作所基礎研究所:(現)京都大学大学院情報学研究科
杉本 晃宏 日立製作所
山口 敦子 日立製作所中央研究所
山口 敦子 日立製作所基礎研究所:(現)生物分子工学研究所
杉本 晃宏 日立製作所基礎研究所
山口 敦子 日立製作所 中央研究所

関連論文