Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2509.16135 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916958317838336 |
|---|---|
| author | Fink, Jiří |
| author_facet | Fink, Jiří |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16135 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant time enumeration of perfect bipartite matchings Fink, Jiří Data Structures and Algorithms F.2 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. |
| title | Constant time enumeration of perfect bipartite matchings |
| topic | Data Structures and Algorithms F.2 |
| url | https://arxiv.org/abs/2509.16135 |