کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419285 | 683773 | 2015 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A characterisation of clique-width through nested partitions
ترجمه فارسی عنوان
توصیف عرض کلاسی از طریق پارتیشن های توپی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کلیدهای عرض، فاصله کلاسی خطی، تعیین مشخصات، نمایندگی کارآمد
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Clique-width of graphs is defined algebraically through operations on graphs with vertex labels. We characterise the clique-width in a combinatorial way by means of partitions of the vertex set, using trees of nested partitions where partitions are ordered bottom-up by refinement. We show that the correspondences in both directions, between combinatorial partition trees and algebraic terms, preserve the tree structures and that they are computable in polynomial time. We apply our characterisation to linear clique-width. And we relate our characterisation to a clique-width characterisation by Heule and Szeider that is used to reduce the clique-width decision problem to a satisfiability problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 187, 31 May 2015, Pages 70–81
Journal: Discrete Applied Mathematics - Volume 187, 31 May 2015, Pages 70–81
نویسندگان
Bruno Courcelle, Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics,