{
  "id": "enwiki-001187569693",
  "slug": "priority-matching",
  "title": "Priority matching",
  "qid": "",
  "lead": "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 , 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 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.…",
  "body": "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 , 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 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 . Jonathan S. Turner 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 graphs: the algorithm runs in time O(k |E| \\sqrt )",
  "categories": [
    "23603337",
    "26220375",
    "29176456"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1187569693",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1701305132.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001187569693",
    "type": "webpage",
    "title": "Priority matching",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/priority-matching",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001187569693",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1187569693",
    "note": "Immutable snapshot enwiki-001187569693"
  }
}