کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141578 957029 2009 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the feedback vertex set polytope of a series–parallel graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
On the feedback vertex set polytope of a series–parallel graph
چکیده انگلیسی

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
نویسندگان
, ,