| Prosenjit Bose y (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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(n | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||