Title: Finding perfect matchings in random regular graphs in linear expected time
| Speaker: | Michael Anastos |
| Affiliation: | Carnegie Mellon University |
| Room: | MC 5501 |
Abstract:
In
a
seminal
paper
on
finding
large
matchings
in
sparse
random
graphs,
Karp
and
Sipser
proposed
two
algorithms
for
this
task.
The
second
algorithm
has
been
intensely
studied,
but
due
to
technical
difficulties,
the
first
algorithm
has
received
less
attention.
Empirical
results
suggest
that
the
first
algorithm
is
superior.
We
show
that
this
is
indeed
the
case,
at
least
for
random
regular
graphs.
We
show
that
w.h.p.
the
first
algorithm
will
find
a
matching
of
size
n/2
- O(log
n)
on
a
random
r-regular
graph
(r
=
O(1)).
We
also
show
that
the
algorithm
can
be
adapted
to
find
a
perfect
matching
w.h.p.
in
O(n)
time,
as
opposed
to
O(n3/2)
time
for
the
worst-case.
The
case
r
=
3
is
based
on
joint
work
with
Alan
Frieze
.