On a Spectral Lower Bound of Treewidth

Tatsuya Gima; Tesshu Hanaka; Kohei Noro; Hirotaka Ono; Yota Otachi

doi:10.1587/transinf.2023FCL0002

On a Spectral Lower Bound of Treewidth

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, Yota Otachi

数理情報

研究成果: ジャーナルへの寄稿 › レター › 査読

1 被引用数 (Scopus)

抄録

In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

本文言語	英語
ページ（範囲）	328-330
ページ数	3
ジャーナル	IEICE Transactions on Information and Systems
巻	E107.D
号	3
DOI	https://doi.org/10.1587/transinf.2023FCL0002
出版ステータス	出版済み - 3月 2024

!!!All Science Journal Classification (ASJC) codes

ソフトウェア
ハードウェアとアーキテクチャ
コンピュータビジョンおよびパターン認識
電子工学および電気工学
人工知能

文献へのアクセス

10.1587/transinf.2023FCL0002

他のファイルとリンク

引用スタイル

@article{73a416f43ab243858811a0d812c7c9fa,

title = "On a Spectral Lower Bound of Treewidth",

abstract = "In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].",

keywords = "Laplacian matrix, algebraic connectivity, eigenvalue, treewidth",

author = "Tatsuya Gima and Tesshu Hanaka and Kohei Noro and Hirotaka Ono and Yota Otachi",

note = "Publisher Copyright: Copyright {\textcopyright} 2024 The Institute of Electronics, Information and Communication Engineers.",

year = "2024",

month = mar,

doi = "10.1587/transinf.2023FCL0002",

language = "English",

volume = "E107.D",

pages = "328--330",

journal = "IEICE Transactions on Information and Systems",

issn = "0916-8532",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "3",

}

TY - JOUR

T1 - On a Spectral Lower Bound of Treewidth

AU - Gima, Tatsuya

AU - Hanaka, Tesshu

AU - Noro, Kohei

AU - Ono, Hirotaka

AU - Otachi, Yota

PY - 2024/3

Y1 - 2024/3

N2 - In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

AB - In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

KW - Laplacian matrix

KW - algebraic connectivity

KW - eigenvalue

KW - treewidth

UR - http://www.scopus.com/inward/record.url?scp=85187101454&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85187101454&partnerID=8YFLogxK

U2 - 10.1587/transinf.2023FCL0002

DO - 10.1587/transinf.2023FCL0002

M3 - Letter

AN - SCOPUS:85187101454

SN - 0916-8532

VL - E107.D

SP - 328

EP - 330

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 3

ER -

On a Spectral Lower Bound of Treewidth

抄録

!!!All Science Journal Classification (ASJC) codes

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル