書誌事項
- タイトル別名
-
- An Approximation Algorithm for the Bipartite Graph Drawing Problem
- 2ブ グラフ ビョウガ モンダイ ニ タイスル キンジ アルゴリズム
- アルゴリズム理論
- 公開日
- 1999-10-15
- 資源種別
- journal article
- 公開者
- 東京 : 情報処理学会
この論文をさがす
説明
2部グラフ描画における辺交差数最小化問題は，NP困難であることが知られている．本稿では，この問題に対する多項式時間近似アルゴリズムを提案し，その近似精度と入力グラフの最大次数との関係を述ベる．最大次数が4以下の場合，本アルゴリズムが出力する解の辺交差数と最適解の辺交差数との比は2以下になり，最大次数が大きくなるにつれてこの値は漸近的に3に近づく．また，計算機実験によって，本アルゴリズムと従来法である重心法やメジアン法とを比較し，頂点数やグラフの最大次数にかかわらず，本アルゴリズムの方が良い解を出力することを示す．
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.
収録刊行物
-
- 情報処理学会論文誌
-
情報処理学会論文誌 40 (10), 3629-3637, 1999-10-15
東京 : 情報処理学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1050845762815469056
-
- NII論文ID
- 110002725111
-
- NII書誌ID
- AN00116647
-
- ISSN
- 18827764
- 03875806
-
- NDL書誌ID
- 4876235
-
- 本文言語コード
- ja
-
- 資料種別
- journal article
-
- データソース種別
-
- IRDB
- NDLサーチ
- CiNii Articles