Improved fixed parameter algorithm for two-layer crossing minimization

• Yasuaki Kobayashi

  Gakushuin University

• Hisao Tamaki

  Meiji University

抄録

We give an algorithm that decides whether the bipartite crossing number of a given graph is at most k. The running time of the algorithm is 2O(k)nO(1), where n is the number of vertices of the input graph, which improves the previous algorithm due to Kobayashi et al. (TCS 2014) that runs in 2O(k log k)nO(1) time. This result is based on a combinarotial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 2015 (9), 1-2, 2015-01-06

  一般社団法人情報処理学会

詳細情報

• CRID: 1573668927629213696
• NII論文ID: 110009864154
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: en
• データソース種別:
  • CiNii Articles