An Interesting Structural Property Related to the Problem of Computing All the Best Swap Edges of a Tree Spanner in Unweighted Graphs

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 availa...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-07
Main Authors: Bilò, Davide, Papadopoulos, Kleitos
Format: Article
Language:English
Subjects:
Apexes
Computation
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(n^2)\) 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.
ISSN:2331-8422