کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903867 | 1632963 | 2018 | 30 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A unified treatment of linked and lean tree-decompositions
ترجمه فارسی عنوان
درمان یکپارچه از تجزیه و تقسیم درخت درختی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تجزیه درخت، تجزیه شعبه، مرتبط، لاغر سیستم جداسازی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
There are many results asserting the existence of tree-decompositions of minimal width which still represent local connectivity properties of the underlying graph, perhaps the best known being Thomas' theorem that proves for every graph G the existence of a linked tree-decomposition of width tw(G). We prove a general theorem on the existence of linked and lean tree-decompositions, providing a unifying proof of many known results in the field, as well as implying some new results. In particular we prove that every matroid M admits a lean tree-decomposition of width tw(M), generalizing the result of Thomas.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 130, May 2018, Pages 114-143
Journal: Journal of Combinatorial Theory, Series B - Volume 130, May 2018, Pages 114-143
نویسندگان
Joshua Erde,