← Back to papers
A distributed blossom algorithm for minimum-weight perfect matching
E. C. Peterson, Peter J. Karalekas·October 25, 2022·DOI: 10.48550/arXiv.2210.14277
Computer Science
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We describe a distributed, asynchronous variant of Edmonds’s exact algorithm for producing perfect matchings of minimum weight [Edm65a]. The development of this algorithm is driven by an application to online error correction in quantum computing, first envisioned by Fowler [FWH12]; we analyze the performance of our algorithm as applied to this domain in a sequel [PK].