Friday, March 20, 2009 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Increasing connectivity of a graph from 1 to 2
| Speaker: | Guy Kortsarz |
|---|---|
| Affiliation: | Rutgers University |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Given an unweighted graph G(V,E) and a set F\subseteq V\times V the goal is to find a minimum SIZE F'\subset F such that G(V,E+F') is 2 edge-connected, namely, every edge lies in a cycle in G(V,E+F').
This
problem
is
one
of
the
most
basic
problems
in
connectivity
augmentation.
We
have
a
(somewhat
complex)
1.5
approximation
algorithm
for
the
problem
(namely
an
algorithm
that
for
every
instance
outputs
a
solution
of
size
no
more
than
1.5
times
the
optimum
solution
for
this
instance).
In
this
talk
we
will
give
some
of
the
details
of
a
significantly
simpler
1.8
approximation
for
the
problem.
The
talk
is
self
contained.