An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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, V1, …, Vk, called priority classes. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from V1; subject to this, it saturates the largest number of vertices from V2; subject to this, it saturates the largest number of vertices from V3; and so on.

Property Value
dbo:abstract
  • 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, V1, …, Vk, called priority classes. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from V1; subject to this, it saturates the largest number of vertices from V2; subject to this, it saturates the largest number of vertices from V3; and so on. Priority matchings were introduced by Alvin Roth, Tayfun Sonmez and in the context of . 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 (en)
dbo:wikiPageID
  • 65198326 (xsd:integer)
dbo:wikiPageLength
  • 3470 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1096976657 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • 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, V1, …, Vk, called priority classes. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from V1; subject to this, it saturates the largest number of vertices from V2; subject to this, it saturates the largest number of vertices from V3; and so on. (en)
rdfs:label
  • Priority matching (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License