Article ID Journal Published Year Pages File Type
10332695 Journal of Computer and System Sciences 2016 9 Pages PDF
Abstract
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).
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,