| Item type |
SIG Technical Reports(1) |
| 公開日 |
2024-03-14 |
| タイトル |
|
|
タイトル |
ラプラシアン行列の固有値を用いた木幅の下界 |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
名古屋大学 |
| 著者所属 |
|
|
|
九州大学 |
| 著者所属 |
|
|
|
名古屋大学 |
| 著者所属 |
|
|
|
名古屋大学 |
| 著者所属 |
|
|
|
名古屋大学 |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu University |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者名 |
儀間, 達也
土中, 哲秀
野呂, 浩平
小野, 廣隆
大舘, 陽太
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本論文では頂点数 n，最大次数 Δ のグラフ G について，ラプラシアン行列の固有値を用いた木幅 tw(G) の下界を二つ示す．一つはラプラシアン行列の二番目に小さい固有値 λ2 を用いた下界で，tw(G)≧nλ2/(Δ+λ2)-1 が成り立つ，というものである．これは Chandran と Subramanian [A spectral lower bound for the treewidth of a graph and its consequences. Inf. Process. Lett., 87(4):195-200, 2003] によって示された下界 tw(G)≧3nλ2/(4Δ+8λ2)-1 の改善となっている．今回示した下界は，特に完全二部グラフ Ka,b に対しては tw(Ka,b)≧min{a,b}-1 を与え，Ka,b の実際の木幅 tw(Ka,b)=min{a,b} よりちょうど 1 だけ小さい値となっている．もう一つはラプラシアン行列の二番目に小さい固有値 λ2 および一番大きい固有値 λn を用いた下界で，tw(G)≧2nλ2/(3λn-λ2)-1 が成り立つ，というものである．この下界は完全グラフ Kn に対してtw(Kn)≧n-1 を与える．これは Kn の実際の木幅 tw(Kn)=n-1 と一致する． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2024-AL-197,
号 6,
p. 1-2,
発行日 2024-03-14
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL24197006.pdf (840.8 kB)
