Optimality computation of the minimum stretch spanning tree problem

作者：

Highlights：

• This paper makes efforts on the lower and upper bound computation so as to determine the optimal values of tree-stretch.

• The optimization approach is applied to several typical and representative graph families, such as the hypercubes Qn, the graph products Km × Kn, Pm × Kn, Cm × Cn, Pm × Cn, Pm × Pn, and Km × Cn.

摘要

•This paper makes efforts on the lower and upper bound computation so as to determine the optimal values of tree-stretch.•The optimization approach is applied to several typical and representative graph families, such as the hypercubes Qn, the graph products Km × Kn, Pm × Kn, Cm × Cn, Pm × Cn, Pm × Pn, and Km × Cn.

论文关键词：Discrete optimization,Spanning tree,Tree spanner,Tree-stretch,Fundamental cycle

论文评审过程：Received 11 April 2019, Revised 15 June 2020, Accepted 28 June 2020, Available online 7 July 2020, Version of Record 7 July 2020.

论文官网地址：https://doi.org/10.1016/j.amc.2020.125502