Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332695 | Journal of Computer and System Sciences | 2016 | 9 Pages |
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
Ioannis Papoutsakis,