کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419214 683753 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lift-and-project ranks of the stable set polytope of joined aa-perfect graphs
ترجمه فارسی عنوان
صفات بالابر و پروژه از مجموعه چند ضلعی پایدار از نمودارهای پیوسته پیوست شده است
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In this paper we study lift-and-project polyhedral operators defined by Lovász and Schrijver and Balas, Ceria and Cornuéjols on the clique relaxation of the stable set polytope of webs. We compute the disjunctive rank of all webs and consequently of antiwebs. We also obtain the disjunctive rank of the antiweb constraints for which the complexity of the separation problem is still unknown. Finally, we use our results to provide bounds of the disjunctive rank of larger classes of graphs as joined aa-perfect graphs, where near-bipartite graphs belong to.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 176–184
نویسندگان
, , ,