کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949881 | 1364262 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterizing width two for variants of treewidth
ترجمه فارسی عنوان
مشخص کردن عرض دو برای انواع عرض درخت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Inspired by the notion of special treewidth, we introduce three natural variants of treewidth, namely spaghetti treewidth, strongly chordal treewidth and directed spaghetti treewidth. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a tree of cycles with additional conditions. Finally, we show that for each kâ¥3, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most k, is not closed under taking minors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 29-46
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 29-46
نویسندگان
Hans L. Bodlaender, Stefan Kratsch, Vincent J.C. Kreuzen, O-joung Kwon, Seongmin Ok,