کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656726 1632974 2016 36 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Packing Steiner trees
ترجمه فارسی عنوان
بسته بندی درختان استینر
کلمات کلیدی
درختان استینر، بسته بندی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Let T be a distinguished subset of vertices in a graph G. A T-Steiner tree is a subgraph of G that is a tree and that spans T. Kriesell conjectured that G contains k pairwise edge-disjoint T-Steiner trees provided that every edge-cut of G that separates T   has size ≥2k≥2k. When T=V(G)T=V(G) a T-Steiner tree is a spanning tree and the conjecture is a consequence of a classic theorem due to Nash-Williams and Tutte. Lau proved that Kriesell's conjecture holds when 2k is replaced by 24k, and recently West and Wu have lowered this value to 6.5k  . Our main result makes a further improvement to 5k+45k+4.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 119, July 2016, Pages 178–213
نویسندگان
, , ,