کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872490 681651 2014 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterization of facets of the hop constrained chain polytope via dynamic programming
ترجمه فارسی عنوان
خصوصیات جنبه های چند ضلعی زنجیره ای محدود شده توسط برنامه های پویا
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result in characterizations of all facet defining 0/±1-inequalities for the hop constrained chain polytope and all facet defining 0/1-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper by Dahl and Gouveia in 2004.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 229-246
نویسندگان
, ,