کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420094 | 683892 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimal separators in extended P4P4-laden graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we use the primeval decomposition tree to compute the minimal separators of some graphs and to describe a linear-time algorithm that lists the minimal separators of extended P4P4-laden graphs, extending an algorithm for P4P4-sparse graphs given by Nikolopoulos and Palios [S.D. Nikolopoulos, L. Palios, Minimal separators in P4P4-sparse graphs, Discrete Math. 306 (3) (2006) 381–392]. We also give bounds on the number and total size of all minimal separators of extended P4P4-laden graphs and some of their subclasses, such as P4P4-tidy and P4P4-lite graphs. Moreover, we show that these bounds are tight for all subclasses considered.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 18, December 2012, Pages 2769–2777
Journal: Discrete Applied Mathematics - Volume 160, Issue 18, December 2012, Pages 2769–2777
نویسندگان
Vagner Pedrotti, Célia Picinin de Mello,