کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10151219 685009 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lower bounds on the mim-width of some graph classes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Lower bounds on the mim-width of some graph classes
چکیده انگلیسی
mim-width is a recent graph width measure that has seen applications in graph algorithms and problems related to propositional satisfiability. In this paper, we show linear lower bounds for the mim-width of strongly chordal split graphs, co-comparability graphs and circle graphs. This improves and refines lower bounds that were known before, some of them only conditionally. In the case of strongly chordal graphs not even a conditional lower bound was known before. All of the bounds given are optimal up to constants.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 28-32
نویسندگان
,