On approximating tree spanners that are breadth first search trees

作者：

Highlights：

• NP-completeness of diameter at most t+1 tree t-spanner problem is used.

• Tree spanners that are BFS trees may not be approximated within log factor.

• Known upper bound for approximation ratio is almost reached.

摘要

•NP-completeness of diameter at most t+1 tree t-spanner problem is used.•Tree spanners that are BFS trees may not be approximated within log factor.•Known upper bound for approximation ratio is almost reached.

论文关键词：Tree spanner,Low stretch,Hardness of approximation,Spanning tree,Distance

论文评审过程：Received 7 June 2015, Revised 2 January 2016, Accepted 1 February 2016, Available online 8 March 2016, Version of Record 1 April 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.02.008