کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141552 | 957020 | 2010 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Network design with weighted degree constraints
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In an undirected graph G=(V,E)G=(V,E) with a weight function w:E×V→Q+w:E×V→Q+, the weighted degree dw(v;E)dw(v;E) of a vertex vv is defined as ∑{w(e,v)∣e∈Eincident tov}. In this paper, we consider a network design problem which has upper-bounds on weighted degrees of vertices as its constraints while the objective is to compute a minimum cost graph with a prescribed connectivity. We propose bi-criteria approximation algorithms based on iterative rounding, which has been successfully applied to the degree-bounded network design problem. A problem of minimizing the maximum weighted degree of vertices is also discussed.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 7, Issue 4, November 2010, Pages 246–255
Journal: Discrete Optimization - Volume 7, Issue 4, November 2010, Pages 246–255
نویسندگان
Takuro Fukunaga, Hiroshi Nagamochi,