WEKO3
アイテム
Greedy描画可能な木の完全な組合せ的特徴づけ
https://ipsj.ixsq.nii.ac.jp/records/210282
https://ipsj.ixsq.nii.ac.jp/records/210282246792ba-3914-4f9f-bc35-e8de97ac376c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL21182001.pdf (875.9 kB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-03-10 | |||||||||||
| タイトル | ||||||||||||
| タイトル | Greedy描画可能な木の完全な組合せ的特徴づけ | |||||||||||
| タイトル | ||||||||||||
| 言語 | en | |||||||||||
| タイトル | A complete combinatorial characterization of greedy-drawable trees | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 群馬大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 群馬大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 群馬大学 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Gunma University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Gunma University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Gunma University | ||||||||||||
| 著者名 |
野坂, 怜哉
× 野坂, 怜哉
× 宮田, 洋行
× 中野, 眞一
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | グラフの greedy 描画は任意の 2 頂点に対し，一方の頂点がもう一方の頂点に近づく近傍を必ず持つような描画であり，目的地に近づくように各頂点でデータを転送し続ける単純なルーティングで目的地にデータを配送することができる条件を満たす描画として盛んに研究されている．例えば，greedy 描画できるグラフを特定する研究が行われており，Nollenburg, Prutkin により，最大次数 4 以下の木に対し，線形時間の greedy 描画可能性判定アルゴリズムが与えられている．それを詳しく検討すると，最大次数 4 以下の木の組合せ的特徴づけも得られるが，greedy 描画可能な最大次数 5 の木の組合せ的特徴づけは知られていない．本稿では，最大次数 5 の木の greedy 描画可能な木の組合せ的な特徴づけを与え，greedy 描画可能な木の組合せ的特徴づけを完成させる． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2021-AL-182, 号 1, p. 1-7, 発行日 2021-03-10 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
