EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Tight Bound on the Size of a Smallest Critical Set for Each Failed Edge in a Tree Spanner

Thomas Erlebach, Kleitos Papadopoulos

Graphs and Combinatorics · 2026-08 · 42 (4)

DOI: 10.1007/s00373-026-03057-1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Graphs and Combinatorics, online erschienen am 17.07.2026. Verfasst von Thomas Erlebach und 1 weiteren Autor:innen. Die Arbeit nennt 4 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A tree t -spanner T of a graph G is a spanning tree with the property that the distance between any pair of nodes in T is at most t times the distance in G . If an edge e in T fails (i.e., is removed from G and T ), the tree breaks into two subtrees $$T_+$$ T + and $$T_-$$ T - . Let $$E_X$$ E X denote the set of edges in G that reconnect $$T_+$$ T + and $$T_-$$ T - . Every edge $$f\in E_X$$ f ∈ E X is a potential swap edge for e that can be used to repair the tree spanner. An edge in $$E_X$$ E X that has the largest stretch among all edges in $$E_X$$ E X when f is used to reconnect $$T_+$$ T + and $$T_-$$ T - is called a critical edge. In this paper, we show that, for every edge e that fails in a tree spanner of an unweighted graph, there is always a set of at most four edges that contains at least one critical edge for every potential swap edge of e . The proof relies on studying the endpoints of a diametrical path in a tree with changing edge weights and may be of independent interest. We also show that there are instances where the smallest critical set has size four.

Zitieren

APA

Erlebach, T., & Papadopoulos, K. (2026). A Tight Bound on the Size of a Smallest Critical Set for Each Failed Edge in a Tree Spanner. Graphs and Combinatorics, 42(4). https://doi.org/10.1007/s00373-026-03057-1

Vancouver

Erlebach T, Papadopoulos K. A Tight Bound on the Size of a Smallest Critical Set for Each Failed Edge in a Tree Spanner. Graphs and Combinatorics. 2026;42(4). doi:10.1007/s00373-026-03057-1

BibTeX
@article{Erlebach2026,
  author = {Erlebach, Thomas and Papadopoulos, Kleitos},
  title = {A Tight Bound on the Size of a Smallest Critical Set for Each Failed Edge in a Tree Spanner},
  journal = {Graphs and Combinatorics},
  year = {2026},
  volume = {42},
  number = {4},
  doi = {10.1007/s00373-026-03057-1}
}
Kostenlos starten →