2018/07/09 by Davide Bilò, Bilò, Davide, Kleitos Papadopoulos +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM
paper · pdf · doi:10.48550/arxiv.1807.03331
arxiv created 2018/07/09 · openalex publication_date 2018/07/09 · arxiv updated 2018/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this draft we prove an interesting structural property related to the problem of computing \em all the best swap edges of a \em tree spanner in unweighted graphs. Previous papers show that the maximum stretch factor of the tree where a failing edge is temporarily swapped with any other available edge that reconnects the tree depends only on the \em critical edge. However, in principle, each of the O(n2) swap edges, where n is the number of vertices of the tree, may have its own critical edge. In this draft we show that there are at most 6 critical edges, i.e., each tree edge e has a \em critical set of size at most 6 such that, a critical edge of each swap edge of e is contained in the critical set.