{"ID":2868931,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.16135","arxiv_id":"2509.16135","title":"Constant time enumeration of perfect bipartite matchings","abstract":"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.","short_abstract":"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 list...","url_abs":"https://arxiv.org/abs/2509.16135","url_pdf":"https://arxiv.org/pdf/2509.16135v1","authors":"[\"Jiří Fink\"]","published":"2025-09-19T16:34:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}