کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10332695 687746 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On approximating tree spanners that are breadth first search trees
ترجمه فارسی عنوان
در تقریبی درختان درخت که درخت اول جستجو هستند
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
,