کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141578 | 957029 | 2009 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the feedback vertex set polytope of a series–parallel graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The minimum weight feedback vertex set problem (FVS) on series–parallel graphs can be solved in O(n)O(n) time by dynamic programming. This solution, however, does not provide a “nice” certificate of optimality. We prove a min–max relation for FVS on series–parallel graphs with no induced subdivision of K2,3K2,3 (a class of graphs containing the outerplanar graphs), thereby establishing the existence of nice certificates for these graphs. Our proof relies on the description of a complete set of inequalities defining the feedback vertex set polytope of a series–parallel graph with no induced subdivision of K2,3K2,3. We also prove that many of the inequalities described are facets of this polytope.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 6, Issue 3, August 2009, Pages 271–287
Journal: Discrete Optimization - Volume 6, Issue 3, August 2009, Pages 271–287
نویسندگان
Samuel Fiorini, Odile Marcotte,