کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428841 | 686943 | 2015 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximate spanning cactus
ترجمه فارسی عنوان
تقریبا کاکتوس پوشش داده شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
• No approximation algorithms are known for computing minimum spanning cactus and bottleneck spanning cactus.
• For minimum spanning cactus approximation algorithm with relative error τ is presented.
• For Bottleneck spanning cactus approximation algorithm with relative error 2τ−12τ−1 is presented.
We study minimum spanning cactus and bottleneck spanning cactus problems with τ-triangle inequality. Both problems are NP-Complete. No approximation algorithms are known for these problems. We present τ approximation algorithm for the first and 2τ−12τ−1 approximation algorithm for the second problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 11, November 2015, Pages 828–832
Journal: Information Processing Letters - Volume 115, Issue 11, November 2015, Pages 828–832
نویسندگان
Alak Kumar Datta,