pith. sign in

arxiv: 1507.02799 · v1 · pith:NAFNIDFXnew · submitted 2015-07-10 · 💻 cs.DS

A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

classification 💻 cs.DS
keywords citealgorithmapproximationgraphpartproblemproofratio
0
0 comments X p. Extension
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.