An algorithm for finding a perfect stable matching was proposed by Gale and Shapley (MPDA):
- Iterative, each iteration, until all vertices are paired
- Vertices from
ask their first unasked preference - Vertices from
choose their first preference from the list of asks - If all vertices from
are paired, terminate
- Vertices from
A corollary of the MPDA algorithm is that every graph with a perfect matching also has a stable perfect matching, and this matching can be calculated in polynomial time, in