کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871116 | 1440178 | 2018 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum size tree-decompositions
ترجمه فارسی عنوان
حداقل اختلاف درختان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study in this paper the problem of computing a tree-decomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed kâ¥1, what is the complexity of computing a tree-decomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed kâ¥4 and polynomial for kâ¤2; for k=3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 109-127
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 109-127
نویسندگان
Bi Li, Fatima Zahra Moataz, Nicolas Nisse, Karol Suchan,