In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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 discret ...
, and a
partition 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,
Tayfun Sonmez and
Utku Unver in the context of
kidney exchange
In humans, the kidneys are two reddish-brown bean-shaped blood-filtering organs that are a multilobar, multipapillary form of mammalian kidneys, usually without signs of external lobulation. They are located on the left and right in the retrope ...
. 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 order 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 ( re ...
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 presented a variation of the augmenting path method (
Edmonds' algorithm
In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an ''optimum branching''). The algorithm is applicable to finding a minimum spanning fore ...
) that finds a priority matching in time . Later, he found a faster algorithm for
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
s: the algorithm runs in time
:
See also
*
Maximum cardinality matching
Maximum cardinality matching is a fundamental problem in graph theory.
We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is ...
*
Rank-maximal matching
Rank-maximal (RM) allocation is a rule for fair division of indivisible items. Suppose we have to allocate some items among people. Each person can rank the items from best to worst. The RM rule says that we have to give as many people as possible ...
References
{{Reflist
Matching (graph theory)