2部グラフ描画に対する近似アルゴリズム  [in Japanese] An approximation algorithm for the bipartite graph drawing problem  [in Japanese]

Search this Article

Author(s)

Abstract

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

The minimum edge crossing problem for bipartite graphs in 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 alborithm to the minimum crossing number, is two, and this ratio monotonically increases to three as the maximum degree becomes high. We also presents our experiemts 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.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 64, 33-40, 1998-09-16

    Information Processing Society of Japan (IPSJ)

References:  9

Codes

  • NII Article ID (NAID)
    110002812153
  • NII NACSIS-CAT ID (NCID)
    AN1009593X
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09196072
  • Data Source
    CJP  NII-ELS 
Page Top