Formally, we are given a graph G = (V, E), and a partition of the vertex-set V into some k subsets, V1, …, Vk, called priority classes.
Priority matchings were introduced by Alvin Roth, Tayfun Sonmez and Utku Unver[1] in the context of kidney exchange.
In this problem, the vertices are patient-donor pairs, and each edge represents a mutual medical compatibility.
Roth, Sonmez and Unver assumed that each priority-class contains a single vertex, i.e., the priority classes induce a total order among the pairs.
Jonathan S. Turner[3] presented a variation of the augmenting path method (Edmonds' algorithm) that finds a priority matching in time O(|V||E|).