Priority matching
In graph theory, a priority matching (also called: maximum priority matching) is a matching that maximizes the number of high-priority vertices that participate in the matching. Formally, we are given a graph "G" = ("V", "E"), and a partition of the vertex-set "V" into some "k" subsets, "V"1, ..., "Vk", called "priority classes". A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from "V"1; subject to this, it saturates the largest number of vertices from "V"2; subject to this, it saturates the largest number of vertices from "V"3; and so on.

Priority matchings were introduced by Alvin Roth, Tayfun Sonmez and Utku Unver in the context of kidney exchange. In this problem, the vertices are patient-donor pairs, and each edge represents a mutual medical compatibility. For example, an edge between pair 1 and pair 2 indicates that donor 1 is compatible with patient 2 and donor 2 is compatible with patient 1. The priority classes correspond to medical priority among patients. For example, some patients are in a more severe condition so they must be matched first. 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.

Later, Yasunori Okumura extended the work to priority-classes that may contain any number of vertices. He also showed how to find a priority matching efficiently using an algorithm for maximum-cardinality matching, with a run-time complexity of O (|V| |E| + |V|2 log |V|).

Jonathan S. Turner presented a variation of the augmenting path method (Edmonds' algorithm) that finds a priority matching in time O (|V| |E|). Later, he found a faster algorithm for bipartite graphs: the algorithm runs in time O("k" |E| |V|1/2).
Q131476
graph theory
Concept
Q1065144
matching
Concept
Q28542
Alvin Roth
PER
Q15126663
Tayfun Sonmez
PER
None
Utku Unver
UNK
None
kidney exchange
UNK
Q369377
total order
Concept
Q65088751
maximum-cardinality matching
UNK
Q6274311
Jonathan S. Turner
PER
Q1752324
Edmonds' algorithm
Concept
Q174733
bipartite graph
Concept
Q104854318
Priority matching
UNK
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
studies