Efficient Algorithms For Petersen's Theorem
Therese C. Biedl, McGill University
A well-known theorem of Petersen states that every 3-regular
bridgeless graph contains a perfect matching. In this talk, we present
efficient algorithms for finding such perfect matchings. Our results
are $\Oh(n \log^4 n)$ time for general graphs and $\Oh(n)$ time for planar
graphs (that is, duals of triangulations). This is significantly faster
than the competition of $\Oh(n^{3/2})$. In addition, we believe that our
algorithms are simpler and more practical than this competition.
(joint work with P. Bose, E. Demaine and A. Lubiw)