Coincidencia de prioridades

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 $k$ subconjuntos, $V₁, ..., Vk$ , 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₁$ ; sujeto a esto, satura el mayor número de vértices de $V₂ ; sujeto a esto$ , satura el mayor número de vértices de $V₃ ; 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 arista representa una compatibilidad médica mutua. Por ejemplo, una arista 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 la 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 camino de aumento ( algoritmo de Edmonds ) que encuentra una coincidencia de prioridad en tiempo $O (| V || E |)$ . Posteriormente, encontró un algoritmo más rápido para grafos bipartitos : el algoritmo se ejecuta en tiempo ^[⁴^] $.$

O(k|E|{\sqrt {|V|}})

Véase también

Referencias

↑ Roth, Alvin E.; Sönmez, Tayfun; Utku Ünver, M. (2005-12-01). "Intercambio de riñones por pares" (PDF) . Journal of Economic Theory . 125 (2): 151– 188. doi : 10.1016/j.jet.2005.04.004 . ISSN 0022-0531 . S2CID 583399 .
↑ Okumura, Yasunori (1 de noviembre de 2014). "Revisión de la asignación de prioridades". Juegos y comportamiento económico . 88 : 242–249 . doi : 10.1016/j.geb.2014.10.007 . ISSN 0899-8256 .
↑ Turner, Jonathan (2015-12-28). "Coincidencias de prioridad máxima [ sic ] ". arXiv : 1512.08555 [ cs.DS ].
↑ Turner, Jonathan (2015-12-31). "Matchings de prioridad de máximo [ sic ] más rápidos en grafos bipartitos". arXiv : 1512.09349 [ cs.DS ].

[1] Roth, Alvin E.; Sönmez, Tayfun; Utku Ünver, M. (2005-12-01). "Intercambio de riñones por pares" (PDF) . Journal of Economic Theory . 125 (2): 151– 188. doi : 10.1016/j.jet.2005.04.004 . ISSN 0022-0531 . S2CID 583399 .

[2] Okumura, Yasunori (1 de noviembre de 2014). "Revisión de la asignación de prioridades". Juegos y comportamiento económico . 88 : 242–249 . doi : 10.1016/j.geb.2014.10.007 . ISSN 0899-8256 .

[3] Turner, Jonathan (2015-12-28). "Coincidencias de prioridad máxima [ sic ] ". arXiv : 1512.08555 [ cs.DS ].

[4] Turner, Jonathan (2015-12-31). "Matchings de prioridad de máximo [ sic ] más rápidos en grafos bipartitos". arXiv : 1512.09349 [ cs.DS ].

[ 1 ]

[ 2 ]

[ 3 ]

[