کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875760 1441985 2017 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A width parameter useful for chordal and co-comparability graphs
ترجمه فارسی عنوان
یک پارامتر عرض برای نمودارهای هماهنگ و همپوشانی مفید است
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,