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

• Item type: Journal(1)
• 公開日: 1999-10-15
• タイトル: 2部グラフ描画問題に対する近似アルゴリズム
• タイトル / 言語: en
• タイトル: An Approximation Algorithm for the Bipartite Graph Drawing Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文（論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: アルゴリズム理論
• 著者所属: 日立製作所基礎研究所／現在，生物分子工学研究所
• 著者所属: 日立製作所基礎研究所／現在，京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Advanced Research Laboratory, Hitachi, Ltd/Presently with Biomolecular Engineering Research Institute
• 著者所属(英): en
• 著者所属(英): Advanced Research Laboratory, Hitachi, Ltd/Presently with Graduate School of Informatics, Kyoto University
• 著者名: 山口, 敦子; 杉本, 晃宏
• 著者名(英): Atsuko, Yamaguchi; Akihiro, Sugimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 2部グラフ描画における辺交差数最小化問題は，NP困難であることが知られている．本稿では，この問題に対する多項式時間近似アルゴリズムを提案し，その近似精度と入力グラフの最大次数との関係を述ベる．最大次数が4以下の場合，本アルゴリズムが出力する解の辺交差数と最適解の辺交差数との比は2以下になり，最大次数が大きくなるにつれてこの値は漸近的に3に近づく．また，計算機実験によって，本アルゴリズムと従来法である重心法やメジアン法とを比較し，頂点数やグラフの最大次数にかかわらず，本アルゴリズムの方が良い解を出力することを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The minimum edge crossings problem for bipartite es known to be NP-hard.This paper presents a polynomial-time approximation algorithm and the relationship between the approximation ratio of our algorithm and the maximum degrees of input graphs.When the maximum degree of a graph is not greater than four,the approximation ratio,i.e.,the maximum ratio of the edge crossing number of the solution constructed by our algorithm to the minimum edge crossing number,is two,and this ratio monotonically increases to three as the maximum degree becomes high.We also present our experiments on comparing the proposed algorithm with the barycenter method and the median method.Our experiments show that the proposed algorithm constructs better solutions than the other methods for dense graphs as well as sparse graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 40, 号 10, p. 3629-3637, 発行日 1999-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764