کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872084 | 681717 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the treewidth of toroidal grids
ترجمه فارسی عنوان
در عرض درخت شبکه های توربو
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درخت عرض شبکه توریدال، برمبلی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the nÃn toroidal grid is either 2nâ2 or 2nâ1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 303-306
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 303-306
نویسندگان
Masashi Kiyomi, Yoshio Okamoto, Yota Otachi,