The Minimum Stretch Spanning Tree Problem for Typical Graphs

• 作者: Lan LIN Yi-xun LIN
• 来源期刊: 应用数学学报（英文版）
• 年，卷（期）: 2021,（3）
• 页码范围: 510-522
• 页数: 13页
• 语种: 英文

摘要

With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The problem has been proved NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs.In this paper,we concentrate on the optimality characteriza-tions for typical classes of graphs.We determine the exact formulae for the complete k-partite graphs,split graphs,generalized convex graphs,and several planar grids,including rectangular grids,triangular grids,and triangulated-rectangular grids.