A Formal Correctness Proof of Edmonds' Blossom Shrinking Algorithm
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909971129565184 |
|---|---|
| author | Abdulaziz, Mohammad Mehlhorn, Kurt |
| author_facet | Abdulaziz, Mohammad Mehlhorn, Kurt |
| contents | We present the first formal correctness proof of Edmonds' blossom shrinking algorithm for maximum cardinality matching in general graphs. We focus on formalising the mathematical structures and properties that allow the algorithm to run in worst-case polynomial running time. We formalise Berge's lemma, blossoms and their properties, and a mathematical model of the algorithm, showing that it is totally correct. We provide the first detailed proofs of many of the facts underlying the algorithm's correctness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20878 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Formal Correctness Proof of Edmonds' Blossom Shrinking Algorithm Abdulaziz, Mohammad Mehlhorn, Kurt Logic in Computer Science Data Structures and Algorithms 68, 90 F.4; F.2 We present the first formal correctness proof of Edmonds' blossom shrinking algorithm for maximum cardinality matching in general graphs. We focus on formalising the mathematical structures and properties that allow the algorithm to run in worst-case polynomial running time. We formalise Berge's lemma, blossoms and their properties, and a mathematical model of the algorithm, showing that it is totally correct. We provide the first detailed proofs of many of the facts underlying the algorithm's correctness. |
| title | A Formal Correctness Proof of Edmonds' Blossom Shrinking Algorithm |
| topic | Logic in Computer Science Data Structures and Algorithms 68, 90 F.4; F.2 |
| url | https://arxiv.org/abs/2412.20878 |