کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872084 681717 2016 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the treewidth of toroidal grids
ترجمه فارسی عنوان
در عرض درخت شبکه های توربو
کلمات کلیدی
درخت عرض شبکه توریدال، برمبلی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , ,