En la teoría de grafos , una coincidencia de prioridad (también llamada: coincidencia de máxima prioridad ) es una coincidencia que maximiza el número de vértices de alta prioridad que participan en la coincidencia. Formalmente, se nos da un gráfico 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 . Una coincidencia de prioridad es una coincidencia que, entre todas las coincidencias 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í.
Los emparejamientos de prioridad fueron introducidos por Alvin Roth , Tayfun Sonmez y Utku Unver [1] en el contexto del intercambio de riñón . En este problema, los vértices son pares de 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 se encuentran 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 prioridades de manera eficiente utilizando un algoritmo para la coincidencia de cardinalidad máxima , con una complejidad en tiempo de ejecución de O (| V | | E | + | V | 2 log | V |).
Jonathan S. Turner [3] presentó una variación del método de camino de aumento ( 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 gráficos bipartitos : el algoritmo se ejecuta en el tiempo O ( k | E | | V | 1/2 ). [4]
Ver también
Referencias
- ^ Roth, Alvin E .; Sönmez, Tayfun; Utku Ünver, M. (1 de diciembre de 2005). "Intercambio de riñón por pares" . Revista de teoría económica . 125 (2): 151–188. doi : 10.1016 / j.jet.2005.04.004 . ISSN 0022-0531 . S2CID 583399 .
- ^ Okumura, Yasunori (1 de noviembre de 2014). "Revisiones de coincidencias de prioridad" . Juegos y comportamiento económico . 88 : 242–249. doi : 10.1016 / j.geb.2014.10.007 . ISSN 0899-8256 .
- ^ Turner, Jonathan (28 de diciembre de 2015). "Coincidencias de máxima prioridad". arXiv : 1512.08555 [ cs.DS ].
- ^ Turner, Jonathan (31 de diciembre de 2015). "Coincidencias de máxima prioridad más rápidas en gráficos bipartitos". arXiv : 1512.09349 [ cs.DS ].