文献

J-GLOBAL ID：201702284542501825   整理番号：17A0544983

交差数の少ない単一ページ描画における固定パラメータアルゴリズム

著者 (3件)： 大塚広夢 (明治大) ,  小林靖明 (京大) ,  玉木久夫 (明治大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2017  号： AL-161  ページ： Vol.2017-AL-161,No.3,1-7 (WEB ONLY)  発行年： 2017年01月10日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフの本型埋め込みの研究は古くから行われ,その拡張として,少ないページ数に少ない辺交差数でグラフを埋め込む問題が考えられている。ここでは,n頂点のグラフGと非負整数kが与えられたとき,Gが1ページに辺の交差数が高々kで埋め込みができるかを判定する問題を考える。この問題はBannisterとEppstein(GD2014)によって固定パラメータ容易であることが示されたが,その結果の中ではCourcelleの定理を用いているため,アルゴリズムやその計算時間は陽に示されていない。本稿では,その判定問題に対する2^{O(k log k)}n時間アルゴリズムを与える。この結果は,既存の手法に対して単純に動的計画法を与えるのではなく,1ページ描画に関する非自明な性質を用いたアルゴリズムである。(著者抄録)

シソーラス用語： *アルゴリズム ,  *グラフ ,  *NP困難 ,  交差 ,  端部 ,  *埋込み【写像】 ,  頂点 ,  *動的計画法 ,  決定問題 ,  計算量 ,  部分集合
準シソーラス用語： グラフアルゴリズム ,  グラフ描画 ,  固定パラメータトラクタビリティ ,  1ページ交差数 ,  グラフ埋込み ,  辺

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (23件)：

• M. J. Bannister, D. Eppstein: Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth. In Proc. of GD 2014, pages 210-221, 2014.
• M. J. Bannister, D. Eppstein, J. A. Simons: Fixed Parameter Tractability of Crossing Minimization of Almost-Trees. In Proc. of GD 2013, pages 340-351, 2013.
• M. Baur, U. Brandes: Crossing Reduction in Circular Layouts. In Proc. of WG 2004, pages 332-343, 2004.
• F. Bernhart, P. C. Kainen: The Book Thickness of a Graph. Journal of Combinatorial Theory, Series B 27, 320-331, 1979.
• G. Blin, G. Fertin, D. Hermelin, S. Vialette: Fixedparameter algorithms for protein similarity search under mRNA structure constraints. Journal of Discrete Algorithms 6(4), 618-626, 2008.

タイトルに関連する用語 (4件)： 交差 ,  描画 ,  パラメータ ,  アルゴリズム