کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332695 | 687746 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On approximating tree spanners that are breadth first search trees
ترجمه فارسی عنوان
در تقریبی درختان درخت که درخت اول جستجو هستند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
دنده درخت کشش کم سختی تقریبی، درخت پوشا، فاصله،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
There are known efficient algorithms that approximate the minimum t for which a graph admits a tree t-spanner with ratio O(logâ¡n). Unless there is an algorithm that decides 3-SAT in quasi-polynomial time, it is impossible to approximate efficiently the minimum t for which a graph admits a tree t-spanner that is a breadth first search tree starting from a given vertex with ratio almost o(logâ¡n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 817-825
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 817-825
نویسندگان
Ioannis Papoutsakis,