WEKO3
アイテム
交差数の少ない単一ページ描画における固定パラメータアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/176529
https://ipsj.ixsq.nii.ac.jp/records/176529e6f5423f-d6dd-4d57-8fa0-a731138cced9
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL17161003.pdf (322.2 kB)
|
Copyright (c) 2017 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2017-01-10 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 交差数の少ない単一ページ描画における固定パラメータアルゴリズム | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 明治大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 明治大学 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Meiji University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Kyoto University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Meiji University | ||||||||||||
| 著者名 |
大塚, 広夢
× 大塚, 広夢
× 小林, 靖明
× 玉木, 久夫
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | グラフの本型埋め込みの研究は古くから行われ，その拡張として，少ないページ数に少ない辺交差数でグラフを埋め込む問題が考えられている．ここでは，n 頂点のグラフ G と非負整数kが与えられたとき，G が 1 ページに辺の交差数が高々 k で埋め込みができるかを判定する問題を考える．この問題は Bannister と Eppstein (GD 2014) によって固定パラメータ容易であることが示されたが，その結果の中では Courcelle の定理を用いているため，アルゴリズムやその計算時間は陽に示されていない．本稿では，その判定問題に対する 2O (k log k) n 時間アルゴリズムを与える．この結果は，既存の手法に対して単純に動的計画法を与えるのではなく，1 ページ描画に関する非自明な性質を用いたアルゴリズムである． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2017-AL-161, 号 3, p. 1-7, 発行日 2017-01-10 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
