کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332910 | 687939 | 2013 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On some network design problems with degree constraints
ترجمه فارسی عنوان
در برخی از مشکلات طراحی شبکه با محدودیت های درجه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
طراحی شبکه، مقررات محدود، الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
⺠For the problem of finding a 2-connected subgraph with degree bounds we give a bicriteria constant approximation. ⺠We give an OË(k/opt) approximation for finding a directed k-tree with minimum outdegree. ⺠We give a constant ratio for the prize collecting version of the second problem. ⺠For Steiner forest with hard degree bounds of 1, we give an O(log3n) ratio.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 79, Issue 5, August 2013, Pages 725-736
Journal: Journal of Computer and System Sciences - Volume 79, Issue 5, August 2013, Pages 725-736
نویسندگان
Rohit Khandekar, Guy Kortsarz, Zeev Nutov,