| Event |
Google Summer of Code, 2025
|
| Project name |
On the Implementation of the \( \mathcal{O}(|E|\cdot\sqrt{|V|}) \) Micali-Vazirani Algorithm
|
| Organization |
SageMath |
| Contributor |
Janmenjaya Panda |
| Mentor(s) |
Prof. David Coudert, Prof. Dima Pasechnik |
| Technologies |
Python, Cython |
| Topics |
Mathematics, Algorithm, Graph Theory, Matchings |
| Project size |
Large |
| Project details |
Matchings and perfect matchings have received considerable attention in graph theory as well as in other related domains (such as, but not limited to, algorithms and optimization). There still remain many open problems — such as Barnette’s conjecture, Berge-Fulkerson conjecture, and so on — due to which it continues to remain an active area of research. At the heart of all this research lies the bottleneck of finding a maximum cardinality matching in undirected graphs. The objective of this project is to implement the Micali-Vazirani algorithm in SageMath — which achieves the best known theoretical runtime of \( \mathcal{O}(|E|\cdot\sqrt{|V|}) \) for computing such a matching — and to make all of this available freely to students, educators as well as researchers all across the world.
|