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

• Item type: SIG Technical Reports(1)
• 公開日: 1998-09-16
• タイトル: 2部グラフ描画に対する近似アルゴリズム
• タイトル / 言語: en
• タイトル: An approximation algorithm for the bipartite graph drawing problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日立製作所基礎研究所
• 著者所属: 日立製作所基礎研究所
• 著者所属(英): en
• 著者所属(英): Advanced Research Laboratory, Hitachi, Ltd.
• 著者所属(英): en
• 著者所属(英): Advanced Research Laboratory, Hitachi, Ltd.
• 著者名: 山口, 敦子; 杉本, 晃宏
• 著者名(英): Atsuko, Yamaguchi; Akihiro, Sugimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 2部グラフ描画における辺交差数最小化問題は，NP困難であることが知られている．本稿では，この問題に対する多項式時間近似アルゴリズムを提案し，その近似精度と入力となるグラフの最大次数との関係を述べる．最大次数が4以下の場合，本アルゴリズムが出力する解の辺交差数と最適解の辺交差数との比は2以下になり，最大次数が大きくなるにつれてこの値は漸近的に3に近づく．また，計算機実験によって，本アルゴリズムと従来法である重心法やメジアン法とを比較し，頂点数やグラフの最大次数にかかわらず，本アルゴリズムの方がよい解を出力することを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The minimum edge crossing problem for bipartite graphs is 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 4, the approximation ratio, i. e. , the maximum ratio of the crossing number of the solution constructed by our algorithm to the minimum crossing number, is two, and this ratio monotonically increases to three as the maximum degree becomes high. We also presents our experiments on comparing our algorithm with the barycenter method or the median method. Our experiments shows that our algorithm constructs better solutions than the other methods for dense graphs as well as sparse graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 78(1998-AL-064), p. 33-40, 発行日 1998-09-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会