کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141821 957094 2006 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Facets of the independent path-matching polytope
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Facets of the independent path-matching polytope
چکیده انگلیسی

Cunningham and Geelen introduced the independent path-matching problem as a common generalization of the weighted matching problem and the weighted matroid intersection problem. Associated with an independent path-matching is an independent path-matching vector. The independent path-matching polytope of an instance of the independent path-matching problem is the convex hull of all the independent path-matching vectors. Cunningham and Geelen described a system of linear inequalities defining the independent path-matching polytope. In this paper, we characterize which inequalities in this system induce facets of the independent path-matching polytope, generalizing previous results on the matching polytope and the common independent set polytope.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 3, Issue 2, 1 June 2006, Pages 111–122
نویسندگان
,