کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656726 | 1632974 | 2016 | 36 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Packing Steiner trees
ترجمه فارسی عنوان
بسته بندی درختان استینر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درختان استینر، بسته بندی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
Journal: Journal of Combinatorial Theory, Series B - Volume 119, July 2016, Pages 178–213
نویسندگان
Matt DeVos, Jessica McDonald, Irene Pivotto,