graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, 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 Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

, and a

partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...

of the vertex-set into some subsets, , called ''priority classes''. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from ; subject to this, it saturates the largest number of vertices from ; subject to this, it saturates the largest number of vertices from ; and so on. Priority matchings were introduced by

Alvin Roth Alvin Eliot Roth (born December 18, 1951) is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the Gund professor of economics and business administration emeritus at Harvard University.

, 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 In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...

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 .

Jonathan S. Turner Jonathan Shields Turner is a senior professor of Computer Science in the Washington University School of Engineering and Applied Science, School of Engineering and Applied Science at Washington University in St. Louis. His research interests incl ...

presented a variation of the augmenting path method ( Edmonds' algorithm) that finds a priority matching in time . Later, he found a faster algorithm for

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

s: the algorithm runs in time :

O(k , E,  \sqrt )

References

{{Reflist Matching (graph theory)

See also

References