Multi-two-edge Connected Subgraph Problems

Abstract:

The minimum cost two-edge connected subgraph problem is an important
problem in network design. Given a network of centres and specific
non-negative costs for connecting any two centres with a link, this
problem consists of finding a cheapest way to construct a network so that
the network remains connected even if one of the links is lost. This
problem has many practical, cost-saving applications, such as the design
of reliable communication and transportation networks. In some
applications, it is useful to allow more than one link (i.e., multi-links)
to be built between a pair of centres in order to build a reliable network
at lower cost.  We will call this the multi-two-edge connected subgraph
problem.

We will present a 3/2-approximation algorithm for the multi-two-edge
connected problem with non-negative costs.  Previously, 2 was the best
known performance guarantee. We will also provide a practical improvement
for the algorithm, and show how the algorithm can be adapted to provide a
3/2-approximation algorithm for the metric two-edge connected and
two-vertex connected subgraph problems.