Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.16135 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We present an algorithm that enumerates all the perfect matchings in a given bipartite graph G = (V,E). Our algorithm requires a constant amortized time to visit one perfect matching of G, in contrast to the current fastest algorithm, published 25 years ago by Uno, which requires O(log |V|) time. To facilitate the listing of all edges in a visited perfect matching, we develop a variant of arithmetic circuits, which may have broader applications in future enumeration algorithms. Consequently, a visited perfect matching is represented within a binary tree. Although it is more common to provide visited objects in an array, we present a class of graphs for which achieving constant amortized time is not feasible in this case.