WEKO3
アイテム
トーラス格子グラフの木幅について
https://ipsj.ixsq.nii.ac.jp/records/241894
https://ipsj.ixsq.nii.ac.jp/records/2418946e0ec7e2-7b25-44bf-94ee-e608b041e813
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL25201006.pdf (861.4 kB)
2027年1月7日からダウンロード可能です。
|
Copyright (c) 2025 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2025-01-07 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | トーラス格子グラフの木幅について | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||
| 資源タイプ | technical report | |||||||||||||
| 著者所属 | ||||||||||||||
| 北海道大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 名古屋大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 名古屋大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 名古屋大学 | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Hokkaido University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Nagoya University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Nagoya University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Nagoya University | ||||||||||||||
| 著者名 |
儀間, 達也
× 儀間, 達也
× 森元, 拓
× 岡田, 優斗
× 大舘, 陽太
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 木幅とは，グラフの木への近さを表すパラメータの一つである．本論文では，トーラス状の n×n 格子グラフの木幅を研究し，n が奇数であるときにその値が 2n-1 であることを示す．Kiyomi らの先行研究 [Discret. Appl. Math. 198 (2016)] は，この値が 2n-1 または 2n-2 であることを示していた．本研究では，先行研究と同様にブランブルと呼ばれる木幅の双対的概念を用い，木幅の下界を構成的に示す．先行研究では多項式個の要素からなるブランブルを構成することで下界 2n-2 を示していたが，本研究では新たな手法を用いて指数個の要素からなるブランブルを構成し，上界に一致する下界 2n-1 を示した． | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN1009593X | |||||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2025-AL-201, 号 6, p. 1-2, 発行日 2025-01-07 |
|||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||||
| Notice | ||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
