کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9516173 | 1343767 | 2005 | 47 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Independence free graphs and vertex connectivity augmentation
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we develop an algorithm which delivers an optimal solution in polynomial time for every fixed k. In the case when the size of an optimal solution is large compared to k, our algorithm is polynomial for all k. We also derive a min-max formula for the size of a smallest augmenting set in this case. A key step in our proofs is a complete solution of the augmentation problem for a new family of graphs which we call k-independence free graphs. We also prove new splitting off theorems for vertex connectivity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 94, Issue 1, May 2005, Pages 31-77
Journal: Journal of Combinatorial Theory, Series B - Volume 94, Issue 1, May 2005, Pages 31-77
نویسندگان
Bill Jackson, Tibor Jordán,