کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903867 1632963 2018 30 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A unified treatment of linked and lean tree-decompositions
ترجمه فارسی عنوان
درمان یکپارچه از تجزیه و تقسیم درخت درختی
کلمات کلیدی
تجزیه درخت، تجزیه شعبه، مرتبط، لاغر سیستم جداسازی،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
نویسندگان
,