کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949679 1440198 2017 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A complete characterization of jump inequalities for the hop-constrained shortest path problem
ترجمه فارسی عنوان
یک ویژگی کامل از نابرابری های پرش برای مشکل کمترین مسافت محدود کمپ
کلمات کلیدی
محدودیت هاپ، کوتاهترین مسیرها، پریدن نابرابری ها، چهره ها، بلند کردن،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Considering an integer k and a directed, weighted graph with two distinct nodes s and  t, the Hop-Constrained Shortest Path Problem looks for a shortest (s,t)-path using at most k arcs. In this paper, we study the polytope of the convex hull of incidence vectors of (s,t)-paths using at most k arcs. We present valid inequalities and adaptations of known concepts such as cloning and a unique representation of facets. The main focus will be on one particular family of valid inequalities, the family of Jump Inequalities. Thereby, the main contribution will be a characterization of the members of the family inducing facets. Furthermore, all possibilities to lift the remaining inequalities will be defined. The analysis of Jump Inequalities will be concluded by further results concerning the equivalence of inequalities as well as their Chvátal rank.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 225, 10 July 2017, Pages 95-113
نویسندگان
,