کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418639 | 681701 | 2010 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The rank-width of the square grid
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Rank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of GG is less than or equal to its branch-width.The n×nn×nsquare grid , denoted by Gn,nGn,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}{1,2,…,n}×{1,2,…,n}, where a vertex (x,y)(x,y) is connected by an edge to a vertex (x′,y′)(x′,y′) if and only if |x−x′|+|y−y′|=1|x−x′|+|y−y′|=1.We prove that the rank-width of Gn,nGn,n is equal to n−1n−1, thus solving an open problem of Oum.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 7, 6 April 2010, Pages 841–850
Journal: Discrete Applied Mathematics - Volume 158, Issue 7, 6 April 2010, Pages 841–850
نویسندگان
Vít Jelínek,