کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875760 | 1441985 | 2017 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A width parameter useful for chordal and co-comparability graphs
ترجمه فارسی عنوان
یک پارامتر عرض برای نمودارهای هماهنگ و همپوشانی مفید است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We generalize these ideas to bigger graph classes. We introduce a new width parameter sim-width, of stronger modeling power than mim-width, by making a small change in the definition of mim-width. We prove that chordal graphs and co-comparability graphs have sim-width at most 1. We investigate a way to bound mim-width for graphs of bounded sim-width by excluding KtâKt and KtâSt as induced minors or induced subgraphs, and give algorithmic consequences. Lastly, we show that circle graphs have unbounded sim-width, and thus also unbounded mim-width.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 704, 15 December 2017, Pages 1-17
Journal: Theoretical Computer Science - Volume 704, 15 December 2017, Pages 1-17
نویسندگان
Dong Yeap Kang, O-joung Kwon, Torstein J.F. Strømme, Jan Arne Telle,