کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950086 | 1440358 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing the Clique-width of Cactus Graphs
ترجمه فارسی عنوان
محاسبه عرض کلاسی نمودارهای کاکتوس
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نظریه گراف، کلیدهای عرض، درخت عرض، پیچیدگی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Similar to the tree-width (twd), the clique-width (cwd) is an invariant of graphs. A well known relationship between tree-width and clique-width is that cwd(G)â¤3â 2twd(G)â1. It is also known that tree-width of Cactus graphs is 2, therefore the clique-width for those graphs is smaller or equal than 6. In this paper, it is shown that the clique-width of Cactus graphs is smaller or equal to 4 and we present a polynomial time algorithm which computes exactly a 4-expression.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 328, 8 December 2016, Pages 47-57
Journal: Electronic Notes in Theoretical Computer Science - Volume 328, 8 December 2016, Pages 47-57
نویسندگان
J. Leonardo González-Ruiz, J. Raymundo Marcial-Romero, J.A. Hernández-ServÃn,