کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419793 | 683861 | 2009 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The box-TDI system associated with 2-edge connected spanning subgraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let GG be a graph and let AA be its cutset-edge incidence matrix. We prove that the linear system 12Ax≥1,x≥0 is box totally dual integral (box-TDI) if and only if GG is a series-parallel graph; a by-product of this characterization is a structural description of a box-TDI system on matroids. Our results strengthen two previous theorems obtained respectively by Cornuéjols, Fonlupt, and Naddef and by Mahjoub which assert that both polyhedra {x∣12Ax≥1,x≥0} and {x∣12Ax≥1,1≥x≥0} are integral if GG is series-parallel.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 1, 6 January 2009, Pages 118–125
Journal: Discrete Applied Mathematics - Volume 157, Issue 1, 6 January 2009, Pages 118–125
نویسندگان
Xujin Chen, Guoli Ding, Wenan Zang,