2部グラフ描画問題に対する近似アルゴリズム  [in Japanese] An Approximation Algorithm for the Bipartite Graph Drawing Problem  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

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.

The minimum edge crossings 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 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.

Journal

  • Transactions of Information Processing Society of Japan

    Transactions of Information Processing Society of Japan 40(10), 3629-3637, 1999-10-15

    Information Processing Society of Japan (IPSJ)

References:  9

Codes

  • NII Article ID (NAID)
    110002725111
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • NDL Article ID
    4876235
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-741
  • Data Source
    CJP  NDL  NII-ELS  IPSJ 
Page Top