A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
pith:NAFNIDFX Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{NAFNIDFX}
Prints a linked pith:NAFNIDFX badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
The Tree Augmentation Problem (TAP) is: given a connected graph $G=(V,{\cal E})$ and an edge set $E$ on $V$ find a minimum size subset of edges $F \subseteq E$ such that $(V,{\cal E} \cup F)$ is $2$-edge-connected. In the conference version \cite{EFKN-APPROX} was sketched a $1.5$-approximation algorithm for the problem. Since a full proof was very complex and long, the journal version was cut into two parts. In the first part \cite{EFKN-TALG} was only proved ratio $1.8$. An attempt to simplify the second part produced an error in \cite{EKN-IPL}. Here we give a correct, different, and self contained proof of the ratio $1.5$, that is also substantially simpler and shorter than the previous proofs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.