En teoría de grafos , un emparejamiento de prioridad (también llamado: emparejamiento de máxima prioridad ) es un emparejamiento que maximiza el número de vértices de alta prioridad que participan en el emparejamiento. Formalmente, se nos da un grafo G = ( V , E ) , y una partición del conjunto de vértices V en algunos k subconjuntos, V 1 , …, V k , llamados clases de prioridad . Un emparejamiento de prioridad es un emparejamiento que, entre todos los emparejamientos posibles, satura el mayor número de vértices de V 1 ; sujeto a esto, satura el mayor número de vértices de V 2 ; sujeto a esto, satura el mayor número de vértices de V 3 ; y así sucesivamente.
Los emparejamientos de prioridad fueron introducidos por Alvin Roth , Tayfun Sonmez y Utku Unver [1] en el contexto del intercambio de riñones . En este problema, los vértices son pares paciente-donante, y cada borde representa una compatibilidad médica mutua. Por ejemplo, un borde entre el par 1 y el par 2 indica que el donante 1 es compatible con el paciente 2 y el donante 2 es compatible con el paciente 1. Las clases de prioridad corresponden a la prioridad médica entre los pacientes. Por ejemplo, algunos pacientes están en una condición más grave, por lo que deben ser emparejados primero. Roth, Sonmez y Unver asumieron que cada clase de prioridad contiene un solo vértice, es decir, las clases de prioridad inducen un orden total entre los pares.
Más tarde, Yasunori Okumura [2] extendió el trabajo a clases de prioridad que pueden contener cualquier número de vértices. También mostró cómo encontrar una coincidencia de prioridad de manera eficiente utilizando un algoritmo para coincidencia de cardinalidad máxima , con una complejidad de tiempo de ejecución de O (| V || E | + | V | 2 log | V |) .
Jonathan S. Turner [3] presentó una variación del método de aumento de trayectorias ( algoritmo de Edmonds ) que encuentra una coincidencia de prioridad en el tiempo O (| V || E |) . Más tarde, encontró un algoritmo más rápido para grafos bipartitos : el algoritmo se ejecuta en el tiempo [4].
