English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Given a 2-edge connected undirected graph $G$ with $n$ vertices and $m$ edges, a $sigma$-tree spanner is a spanning tree of $G$ in which the ratio between the distance in $T$ of any pair of vertices and the corresponding distance in $G$ is upper bounded by $sigma$. The minimum value of $sigma$ for which $T$ is a $sigma$-tree spanner of $G$ is also called the {em stretch factor} of $T$. We address the fault-tolerant scenario in which each edge $e$ of a given tree spanner may temporarily fail and has to be replaced by a {em best swap edge}, i.e. an edge that reconnects $T-e$ at a minimum stretch factor. More precisely, we design an $O(n^2)$ time and space algorithm that computes a best swap edge of every tree edge. Previously, an $O(n^2 log^4 n)$ time and $O(n^2+mlog^2n)$ space algorithm was known for edge-weighted graphs (Bil`o et al., ISAAC 2017). Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a $o(n^2)$ time and space algorithm would be considered a breakthrough.

A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners