Paper by Erik D. Demaine
- Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, and Anna Lubiw, “Efficient Algorithms for Petersen's Matching Theorem”, Journal of Algorithms, volume 38, 2001, pages 110–134. Special issue of selected papers from the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000.
Petersen's theorem is a classic result in matching theory from 1891, stating
that every 3-regular bridgeless graph has a perfect matching. Our work
explores efficient algorithms for finding perfect matchings in such graphs.
Previously, the only relevant matching algorithms were for general graphs, and
the fastest algorithm ran in O(n3/2) time for
3-regular graphs. We have developed an
O(n log4 n)-time algorithm for
perfect matching in a 3-regular bridgeless graph. When the graph is also
planar, we have as the main result of our paper an optimal
O(n)-time algorithm. We present three applications of this
result: terrain guarding, adaptive mesh refinement, and quadrangulation.
- The paper is \copyright Academic Press.
- The paper is 23 pages.
- The paper is available in PostScript (559k) and gzipped PostScript (134k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- MatchingBounds_DM (Tight Bounds on Maximal and Maximum Matchings)
- SODA99b (Efficient Algorithms for Petersen's Matching Theorem)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by