کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481653 | 1446180 | 2008 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given arbitrary source and target nodes s, t and an s–t-flow defined by its flow-values on each arc of a network, we consider the problem of finding a decomposition of this flow with a minimal number of s–t-paths. This problem is issued from the engineering of telecommunications networks for which the task of implementing a routing solution consists in integrating a set of end-to-end paths. We show that this problem is NP-hard in the strong sense and give some properties of an optimal solution. We then propose upper and lower bounds for the number of paths in an optimal solution. Finally we develop two heuristics based on the properties of a special set of solutions called saturating solutions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 185, Issue 3, 16 March 2008, Pages 1390–1401
Journal: European Journal of Operational Research - Volume 185, Issue 3, 16 March 2008, Pages 1390–1401
نویسندگان
B. Vatinlen, F. Chauvet, P. Chrétienne, P. Mahey,