کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9514585 | 1632609 | 2005 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graph decompositions for cartesian products
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we describe an algorithmic construction that, given a tree-decomposition of a graph G and a path-decomposition of a graph H, provides a tree-decomposition of the cartesian product of G and H. From the latter, we derive upper bounds on the treewidth and on the pathwidth of the cartesian product, expressed in terms of the treewidth and of the pathwidth of the two involved graphs. On the other hand, in the context of graph grammars and graph logic, we prove that the cartesian product of a class of graphs by a finite set of graphs preserves the property of being a context-free set, and if the graphs in the finite set are all connected, the property of being an MS-definable set is also preserved.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 375-381
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 375-381
نویسندگان
Selma Djelloul,