A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization

• Item type: SIG Technical Reports(1)
• 公開日: 2012-09-27
• タイトル: A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• タイトル / 言語: en
• タイトル: A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Meiji University
• 著者所属: Meiji University
• 著者所属(英): en
• 著者所属(英): Meiji University
• 著者所属(英): en
• 著者所属(英): Meiji University
• 著者名: Yasuaki, Kobayashi; Hisao, Tamaki
• 著者名(英): Yasuaki, Kobayashi; Hisao, Tamaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in O(3√2k + n) time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of O(√k) in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in 2O(√k log k) + nO(1) time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in O(3√2k + n) time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of O(√k) in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in 2O(√k log k) + nO(1) time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2012-AL-141, 号 1, p. 1-5, 発行日 2012-09-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会