Algoritmo de Hopcroft-Karp

Algoritmo para la correspondencia de máxima cardinalidad

En informática , el algoritmo Hopcroft–Karp (a veces llamado con más precisión algoritmo Hopcroft–Karp–Karzanov ) ^[1] es un algoritmo que toma un gráfico bipartito como entrada y produce una coincidencia de cardinalidad máxima como salida: un conjunto de tantos bordes como sea posible con la propiedad de que ningún par de bordes comparta un punto final. Se ejecuta en el tiempo en el peor de los casos , donde es el conjunto de bordes en el gráfico, es el conjunto de vértices del gráfico y se supone que . En el caso de gráficos densos , el límite de tiempo se convierte en , y para gráficos aleatorios dispersos se ejecuta en el tiempo con alta probabilidad. ^[2] ${\displaystyle O(|E|{\sqrt {|V|}})}$ ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle |E|=\Omega (|V|)}$ ${\displaystyle O(|V|^{2.5})}$ ${\displaystyle O(|E|\log |V|)}$

El algoritmo fue descubierto por John Hopcroft y Richard Karp  (1973) e independientemente por Alexander Karzanov  (1973). ^[3] Al igual que en métodos anteriores para emparejamiento como el algoritmo húngaro y el trabajo de Edmonds (1965), el algoritmo Hopcroft-Karp aumenta repetidamente el tamaño de un emparejamiento parcial al encontrar caminos de aumento . Estos caminos son secuencias de aristas del grafo, que alternan entre aristas en el emparejamiento y aristas fuera del emparejamiento parcial, y donde la arista inicial y final no están en el emparejamiento parcial. Encontrar un camino de aumento nos permite incrementar el tamaño del emparejamiento parcial, simplemente alternando las aristas del camino de aumento (poniendo en el emparejamiento parcial aquellas que no lo estaban, y viceversa). Los algoritmos más simples para el emparejamiento bipartito, como el algoritmo Ford-Fulkerson , encuentran un camino de aumento por iteración; el algoritmo Hopcroft-Karp, en cambio, encuentra un conjunto máximo de caminos de aumento más cortos, de modo de garantizar que solo se necesiten iteraciones en lugar de iteraciones. Se puede lograr el mismo rendimiento para encontrar emparejamientos de máxima cardinalidad en grafos arbitrarios, con el algoritmo más complicado de Micali y Vazirani. ^[4] ${\displaystyle O({\sqrt {|V|}})}$ ${\displaystyle O(|V|)}$ ${\displaystyle O(|E|{\sqrt {|V|}})}$

El algoritmo de Hopcroft-Karp puede considerarse un caso especial del algoritmo de Dinic para el problema de flujo máximo . ^[5]

Ampliando caminos

Un vértice que no es el punto final de una arista en alguna coincidencia parcial se denomina vértice libre . El concepto básico en el que se basa el algoritmo es el de una ruta de aumento , una ruta que comienza en un vértice libre, termina en un vértice libre y alterna entre aristas no coincidentes y coincidentes dentro de la ruta. De esta definición se deduce que, a excepción de los puntos finales, todos los demás vértices (si los hay) en la ruta de aumento deben ser vértices no libres. Una ruta de aumento podría constar de solo dos vértices (ambos libres) y una única arista no coincidente entre ellos. ${\displaystyle M}$

Si es una coincidencia, y es una ruta de aumento relativa a , entonces la diferencia simétrica de los dos conjuntos de aristas, , formaría una coincidencia con tamaño . Por lo tanto, al encontrar rutas de aumento, un algoritmo puede aumentar el tamaño de la coincidencia. ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle M\oplus P}$ ${\displaystyle |M|+1}$

Por el contrario, supongamos que una coincidencia no es óptima, y ​​sea la diferencia simétrica donde es una coincidencia óptima. Como y son ambas coincidencias, cada vértice tiene grado como máximo 2 en . Por lo que debe formar una colección de ciclos disjuntos, de caminos con un número igual de aristas coincidentes y no coincidentes en , de caminos de aumento para , y de caminos de aumento para ; pero esto último es imposible porque es óptimo. Ahora, los ciclos y los caminos con un número igual de vértices coincidentes y no coincidentes no contribuyen a la diferencia de tamaño entre y , por lo que esta diferencia es igual al número de caminos de aumento para en . Por lo tanto, siempre que exista una coincidencia mayor que la coincidencia actual , también debe existir un camino de aumento. Si no se puede encontrar un camino de aumento, un algoritmo puede terminar de manera segura, ya que en este caso debe ser óptimo. ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle M\oplus M^{*}}$ ${\displaystyle M^{*}}$ ${\displaystyle M}$ ${\displaystyle M^{*}}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M^{*}}$ ${\displaystyle M^{*}}$ ${\displaystyle M}$ ${\displaystyle M^{*}}$ ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle M^{*}}$ ${\displaystyle M}$ ${\displaystyle M}$

Un camino de aumento en un problema de emparejamiento está estrechamente relacionado con los caminos de aumento que surgen en los problemas de flujo máximo , caminos a lo largo de los cuales se puede aumentar la cantidad de flujo entre los terminales del flujo. Es posible transformar el problema de emparejamiento bipartito en una instancia de flujo máximo, de modo que los caminos alternativos del problema de emparejamiento se conviertan en caminos de aumento del problema de flujo. Basta con insertar dos vértices, fuente y sumidero, e insertar aristas de capacidad unitaria desde la fuente hasta cada vértice en , y desde cada vértice en hasta el sumidero; y dejar que las aristas de a tengan capacidad unitaria. ^[6] Una generalización de la técnica utilizada en el algoritmo de Hopcroft-Karp para encontrar el flujo máximo en una red arbitraria se conoce como algoritmo de Dinic . ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$

Algoritmo

El algoritmo puede expresarse en el siguiente pseudocódigo .

Entrada : Gráfico bipartito ${\displaystyle G(U\cup V,E)}$

Salida : Coincidencia ${\displaystyle M\subseteq E}$

${\displaystyle M\leftarrow \emptyset }$

repetir

${\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}$ conjunto máximo de caminos de aumento más cortos disjuntos entre vértices

${\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}$

hasta ${\displaystyle {\mathcal {P}}=\emptyset }$

En más detalle, sean y los dos conjuntos en la bipartición de , y sea la correspondencia de a en cualquier momento representada como el conjunto . El algoritmo se ejecuta en fases. Cada fase consta de los siguientes pasos. ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle M}$

• Una búsqueda en amplitud divide los vértices del grafo en capas. Los vértices libres en se utilizan como vértices iniciales de esta búsqueda y forman la primera capa de la partición. En el primer nivel de la búsqueda, solo hay aristas no coincidentes, ya que los vértices libres en por definición no son adyacentes a ninguna arista coincidente. En los niveles posteriores de la búsqueda, se requiere que las aristas recorridas alternen entre coincidentes y no coincidentes. Es decir, cuando se buscan sucesores desde un vértice en , solo se pueden recorrer aristas no coincidentes, mientras que desde un vértice en solo se pueden recorrer aristas coincidentes. La búsqueda termina en la primera capa donde se alcanzan uno o más vértices libres en . ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle V}$
• Todos los vértices libres de una capa se agrupan en un conjunto . Es decir, se incluye un vértice si y solo si termina en un camino de aumento más corto. ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle F}$ ${\displaystyle v}$ ${\displaystyle F}$
• El algoritmo encuentra un conjunto máximo de rutas de aumento disjuntas de vértices de longitud . ( Máximo significa que no se pueden agregar más rutas de este tipo. Esto es diferente de encontrar el número máximo de tales rutas, lo que sería más difícil de hacer. Afortunadamente, aquí es suficiente encontrar un conjunto máximo de rutas). Este conjunto se puede calcular mediante una búsqueda en profundidad (DFS) desde hasta los vértices libres en , utilizando la estratificación en anchura para guiar la búsqueda: la DFS solo puede seguir los bordes que conducen a un vértice no utilizado en la capa anterior, y las rutas en el árbol DFS deben alternar entre bordes coincidentes y no coincidentes. Una vez que se encuentra una ruta de aumento que involucra uno de los vértices en , la DFS continúa desde el siguiente vértice de inicio. Cualquier vértice encontrado durante la DFS se puede marcar inmediatamente como usado, ya que si no hay una ruta desde él hasta en el punto actual en la DFS, entonces ese vértice no se puede usar para llegar a ningún otro punto en la DFS. Esto asegura el tiempo de ejecución para la DFS. También es posible trabajar en la dirección opuesta, desde los vértices libres en hasta los de , que es la variante utilizada en el pseudocódigo. ${\displaystyle k}$ ${\displaystyle F}$ ${\displaystyle U}$ ${\displaystyle F}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle O(|E|)}$ ${\displaystyle U}$ ${\displaystyle V}$
• Cada uno de los caminos que se encuentran de esta manera se utiliza para agrandar . ${\displaystyle M}$

El algoritmo finaliza cuando no se encuentran más rutas de aumento en la parte de búsqueda en amplitud de una de las fases.

Análisis

Cada fase consta de una única búsqueda en amplitud y una única búsqueda en profundidad. Por lo tanto, se puede implementar una única fase en el tiempo. Por lo tanto, las primeras fases, en un grafo con vértices y aristas, toman tiempo . ${\displaystyle O(|E|)}$ ${\displaystyle {\sqrt {|V|}}}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$ ${\displaystyle O(|E|{\sqrt {|V|}})}$

Cada fase incrementa la longitud del camino de aumento más corto en al menos uno: la fase encuentra un conjunto máximo de caminos de aumento de la longitud dada, por lo que cualquier camino de aumento restante debe ser más largo. Por lo tanto, una vez que se completan las fases iniciales del algoritmo, el camino de aumento restante más corto tiene al menos aristas. Sin embargo, la diferencia simétrica del emparejamiento óptimo final y del emparejamiento parcial M encontrado por las fases iniciales forma una colección de caminos de aumento disjuntos en vértices y ciclos alternos. Si cada uno de los caminos en esta colección tiene una longitud de al menos , puede haber como máximo caminos en la colección, y el tamaño del emparejamiento óptimo puede diferir del tamaño de en como máximo aristas. Dado que cada fase del algoritmo incrementa el tamaño del emparejamiento en al menos uno, puede haber como máximo fases adicionales antes de que el algoritmo termine. ${\displaystyle {\sqrt {|V|}}}$ ${\displaystyle {\sqrt {|V|}}}$ ${\displaystyle {\sqrt {|V|}}}$ ${\displaystyle {\sqrt {|V|}}}$ ${\displaystyle M}$ ${\displaystyle {\sqrt {|V|}}}$ ${\displaystyle {\sqrt {|V|}}}$

Dado que el algoritmo realiza un total de como máximo fases, tarda un tiempo total de en el peor de los casos. ${\displaystyle 2{\sqrt {|V|}}}$ ${\displaystyle O(|E|{\sqrt {|V|}})}$

Sin embargo, en muchos casos, el tiempo que tarda el algoritmo puede ser incluso más rápido que lo que indica este análisis del peor de los casos. Por ejemplo, en el caso promedio de los grafos aleatorios bipartitos dispersos , Bast et al. (2006) (mejorando un resultado previo de Motwani 1994) demostraron que con alta probabilidad todos los emparejamientos no óptimos tienen caminos de aumento de longitud logarítmica . Como consecuencia, para estos grafos, el algoritmo de Hopcroft-Karp toma fases y tiempo total. ${\displaystyle O(\log |V|)}$ ${\displaystyle O(|E|\log |V|)}$

Comparación con otros algoritmos de emparejamiento bipartito

Para gráficos dispersos , el algoritmo Hopcroft–Karp sigue teniendo el mejor rendimiento conocido en el peor de los casos, pero para gráficos densos ( ) un algoritmo más reciente de Alt et al. (1991) logra un límite de tiempo ligeramente mejor, . Su algoritmo se basa en el uso de un algoritmo de flujo máximo push-relabel y luego, cuando la coincidencia creada por este algoritmo se acerca al óptimo, cambia al método Hopcroft–Karp. ${\displaystyle |E|=\Omega (|V|^{2})}$ ${\displaystyle O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)}$

Varios autores han realizado comparaciones experimentales de algoritmos de emparejamiento bipartito. Sus resultados en general tienden a mostrar que el método Hopcroft-Karp no es tan bueno en la práctica como lo es en teoría: es superado tanto por estrategias más simples de búsqueda de rutas ampliadas en amplitud y profundidad, como por técnicas de reetiquetado por inserción. ^[7]

Grafos no bipartitos

La misma idea de encontrar un conjunto máximo de caminos de aumento más cortos funciona también para encontrar emparejamientos de cardinalidad máxima en grafos no bipartitos, y por las mismas razones los algoritmos basados ​​en esta idea toman fases. Sin embargo, para grafos no bipartitos, la tarea de encontrar los caminos de aumento dentro de cada fase es más difícil. Basándose en el trabajo de varios predecesores más lentos, Micali y Vazirani (1980) mostraron cómo implementar una fase en tiempo lineal, lo que resultó en un algoritmo de emparejamiento no bipartito con el mismo límite de tiempo que el algoritmo Hopcroft-Karp para grafos bipartitos. La técnica de Micali-Vazirani es compleja, y sus autores no proporcionaron pruebas completas de sus resultados; posteriormente, Peterson y Loui (1988) publicaron una "exposición clara" y otros autores describieron métodos alternativos. ^[8] En 2012, Vazirani ofreció una nueva prueba simplificada del algoritmo Micali-Vazirani. ^[9] ${\displaystyle O({\sqrt {|V|}})}$

Pseudocódigo

/* G = U ∪ V ∪ {NUL} donde U y V son los lados izquierdo y derecho del gráfico bipartito y NIL es un vértice nulo especial*/ La función BFS() es  para cada u en U si Pair_U[u] = NIL entonces Dist[u] := 0 Poner en cola(Q, u) demás Dist[u] := ∞ Dist[NIL] := ∞ mientras Vacío(Q) = falso hacer u := Quitar de cola(Q) si Dist[u] < Dist[NIL] entonces  para cada v en Aj[u] haz  si Dist[Pair_V[v]] = ∞ entonces Dist[Par_V[v]] := Dist[u] + 1 Poner en cola (Q, Par_V[v]) devuelve Dist[NIL] ≠ ∞La función DFS(u) es  si u ≠ NIL entonces  para cada v en Adj[u] hacer  si Dist[Pair_V[v]] = Dist[u] + 1 entonces  si DFS(Pair_V[v]) = verdadero entonces Par_V[v] := u Par_U[u] := v devuelve verdadero Dist[u] := ∞ devuelve falso devuelve verdaderoLa función Hopcroft – Karp es  para cada u en U. Par_U[u] := NIL para cada v en V hacer Par_V[v] := NIL Coincidencia := 0 mientras BFS() = verdadero hacer  para cada u en U hacer  si Pair_U[u] = NIL entonces  si DFS(u) = verdadero entonces coincidencia := coincidencia + 1 devolver coincidencia

Ejecución en un gráfico de ejemplo que muestra el gráfico de entrada y la coincidencia después de la iteración intermedia 1 y la iteración final 2.

Explicación

Dejemos que los vértices de nuestro grafo se particionen en U y V, y consideremos una coincidencia parcial, como lo indican las tablas Pair_U y Pair_V que contienen el vértice con el que se coincide cada vértice de U y de V, o NIL para los vértices no coincidentes. La idea clave es agregar dos vértices ficticios en cada lado del grafo: uDummy conectado a todos los vértices no coincidentes en U y vDummy conectado a todos los vértices no coincidentes en V. Ahora, si ejecutamos una búsqueda en amplitud (BFS) de uDummy a vDummy, entonces podemos obtener las rutas de longitud mínima que conectan los vértices actualmente no coincidentes en U con los vértices actualmente no coincidentes en V. Tenga en cuenta que, como el grafo es bipartito, estas rutas siempre alternan entre vértices en U y vértices en V, y requerimos en nuestra BFS que cuando vayamos de V a U, siempre seleccionemos una arista coincidente. Si llegamos a un vértice no coincidente de V, entonces terminamos en vDummy y la búsqueda de caminos en el BFS termina. Para resumir, el BFS comienza en vértices no coincidentes en U, va a todos sus vecinos en V, si todos coinciden entonces vuelve a los vértices en U con los que coinciden todos estos vértices (y que no fueron visitados antes), luego va a todos los vecinos de estos vértices, etc., hasta que uno de los vértices alcanzados en V no coincide.

Observe en particular que BFS marca los nodos no coincidentes de U con una distancia 0, luego incrementa la distancia cada vez que regresa a U. Esto garantiza que las rutas consideradas en BFS tengan una longitud mínima para conectar vértices no coincidentes de U con vértices no coincidentes de V mientras siempre regresan de V a U en los bordes que actualmente son parte de la coincidencia. En particular, al vértice especial NIL, que corresponde a vDummy, se le asigna una distancia finita, por lo que la función BFS devuelve verdadero solo si se ha encontrado alguna ruta. Si no se ha encontrado ninguna ruta, entonces no quedan rutas de aumento y la coincidencia es máxima.

Si BFS devuelve verdadero, entonces podemos continuar y actualizar el emparejamiento de los vértices en las rutas de longitud mínima encontradas de U a V: lo hacemos usando una búsqueda en profundidad (DFS). Tenga en cuenta que cada vértice en V en dicha ruta, excepto el último, está actualmente emparejado. Por lo tanto, podemos explorar con la DFS, asegurándonos de que las rutas que seguimos corresponden a las distancias calculadas en la BFS. Actualizamos a lo largo de cada una de esas rutas eliminando de la coincidencia todos los bordes de la ruta que están actualmente en la coincidencia, y agregando a la coincidencia todos los bordes de la ruta que actualmente no están en la coincidencia: como se trata de una ruta de aumento (los primeros y últimos bordes de la ruta no eran parte de la coincidencia, y la ruta alternaba entre bordes coincidentes y no coincidentes), entonces esto aumenta el número de bordes en la coincidencia. Esto es lo mismo que reemplazar la coincidencia actual por la diferencia simétrica entre la coincidencia actual y la ruta completa.

Nótese que el código garantiza que todas las rutas de aumento que consideramos sean disjuntas en sus vértices. De hecho, después de hacer la diferencia simétrica para una ruta, ninguno de sus vértices podría considerarse nuevamente en el DFS, simplemente porque Dist[Pair_V[v]] no será igual a Dist[u] + 1 (sería exactamente Dist[u]).

Observe también que el DFS no visita el mismo vértice varias veces. Esto se debe a las siguientes líneas:

Dist[u] = ∞devuelve falso

Cuando no pudimos encontrar ninguna ruta de aumento más corta desde un vértice u, entonces el DFS marca el vértice u estableciendo Dist[u] en infinito, de modo que estos vértices no se visiten nuevamente.

Una última observación es que en realidad no necesitamos uDummy: su función es simplemente poner todos los vértices no coincidentes de U en la cola cuando iniciamos el BFS. En cuanto a vDummy, se denota como NIL en el pseudocódigo anterior.

Véase también

• Coincidencia de cardinalidad máxima , el problema resuelto por el algoritmo y su generalización a grafos no bipartitos
• Problema de asignación , una generalización de este problema en gráficos ponderados, resuelto, por ejemplo, mediante el algoritmo húngaro.
• Algoritmo de Edmonds-Karp para hallar el caudal máximo, una generalización del algoritmo de Hopcroft-Karp

Notas

1. Gabow (2017); Annamalai (2018)
2. Bast y otros (2006).
3. Dinitz (2006).
4. Peterson y Loui (1988).
5. Tarjan (1983), pág. 102.
6. Ahuja, Magnanti y Orlin (1993), sección 12.3, problema de correspondencia de cardinalidad bipartita, págs. 469-470.
7. Chang y McCormick (1990); Darby-Dowman (1980); Setúbal (1993); Setúbal (1996).
8. Gabow y Tarjan (1991).
9. Vazirani (2012)

Referencias

• Ahuja, Ravindra K.; Magnanti , Thomas L .; Orlin, James B. (1993), Flujos de red: teoría, algoritmos y aplicaciones , Prentice-Hall.
• Alt, H.; Blum, N.; Mehlhorn, K .; Paul, M. (1991), "Cálculo de una correspondencia de cardinalidad máxima en un gráfico bipartito en el tiempo ", Information Processing Letters , 37 (4): 237–240, doi :10.1016/0020-0190(91)90195-N ${\displaystyle \scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)}$.
• Annamalai, Chidambaram (2018), "Encontrar correspondencias perfectas en hipergrafos bipartitos", Combinatorica , 38 (6): 1285–1307, arXiv : 1509.07007 , doi :10.1007/s00493-017-3567-2, MR  3910876, S2CID  1997334
• Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao (2006), "Los algoritmos de emparejamiento son rápidos en gráficos aleatorios dispersos", Theory of Computing Systems , 39 (1): 3–14, CiteSeerX  10.1.1.395.6643 , doi :10.1007/s00224-005-1254-y, MR  2189556, S2CID  9321036
• Chang, S. Frank; McCormick, S. Thomas (1990), Una implementación más rápida de un algoritmo de coincidencia de cardinalidad bipartita , Tech. Rep. 90-MSC-005, Facultad de Comercio y Administración de Empresas, Univ. de Columbia BritánicaComo lo cita Setubal (1996).
• Darby-Dowman, Kenneth (1980), La explotación de la escasez en problemas de programación lineal a gran escala – Estructuras de datos y algoritmos de reestructuración , tesis doctoral, Brunel UniversityComo lo cita Setubal (1996).
• Dinitz, Yefim (2006), "El algoritmo de Dinitz: la versión original y la versión de Even", en Goldreich, Oded ; Rosenberg, Arnold L. ; Selman, Alan L. (eds.), Theoretical Computer Science: Essays in Memory of Shimon Even (PDF) , Lecture Notes in Computer Science, vol. 3895, Berlín y Heidelberg: Springer, pp. 218–240, doi :10.1007/11685654_10, ISBN 978-3-540-32880-3.
• Edmonds, Jack (1965), "Caminos, árboles y flores", Revista canadiense de matemáticas , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , MR  0177907, S2CID  18909734.
• Gabow, Harold N. (2017), "El enfoque de emparejamiento ponderado para el emparejamiento de máxima cardinalidad", Fundamenta Informaticae , 154 (1–4): 109–130, arXiv : 1703.03998 , doi :10.3233/FI-2017-1555, MR  3690573, S2CID  386509
• Gabow, Harold N. ; Tarjan, Robert E. (1991), "Algoritmos de escalamiento más rápidos para problemas generales de correspondencia de grafos", Journal of the ACM , 38 (4): 815–853, doi : 10.1145/115234.115366 , S2CID  18350108.
• Hopcroft, John E. ; Karp, Richard M. (1973), "Un algoritmo n ^5/2 para emparejamientos máximos en grafos bipartitos", SIAM Journal on Computing , 2 (4): 225–231, doi :10.1137/0202019. Previamente anunciado en el 12º Simposio Anual sobre Teoría de Conmutación y Autómatas, 1971.
• Karzanov, AV (1973), "Una estimación exacta de un algoritmo para encontrar un flujo máximo, aplicado al problema de los representantes", Problemas en cibernética , 5 : 66–70. Previamente anunciado en el Seminario de Matemática Combinatoria (Moscú, 1971).
• Micali, S. ; Vazirani, VV (1980), "Un algoritmo para encontrar la máxima coincidencia en gráficos generales", Proc. 21st IEEE Symp. Foundations of Computer Science , págs. 17–27, doi :10.1109/SFCS.1980.12, S2CID  27467816 ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}$.
• Peterson, Paul A.; Loui, Michael C. (noviembre de 1988), "El algoritmo general de coincidencia máxima de Micali y Vazirani", Algorithmica , 3 (1–4): 511–533, CiteSeerX  10.1.1.228.9625 , doi :10.1007/BF01762129, ISSN  1432 -0541, S2CID  16820.
• Motwani, Rajeev (1994), "Análisis de casos promedio de algoritmos para emparejamientos y problemas relacionados", Journal of the ACM , 41 (6): 1329–1356, doi : 10.1145/195613.195663 , S2CID  2968208.
• Setubal, João C. (1993), "Nuevos resultados experimentales para el emparejamiento bipartito", Proc. Netflow93 , Departamento de Informática, Univ. de Pisa, págs. 211-216Como lo cita Setubal (1996).
• Setubal, João C. (1996), Resultados experimentales secuenciales y paralelos con algoritmos de emparejamiento bipartito , Tech. Rep. IC-96-09, Inst. de Computación, Univ. de Campinas, CiteSeerX  10.1.1.48.3539.
• Tarjan, Robert Endre (1983). Estructuras de datos y algoritmos de red . Serie de conferencias regionales CBMS-NSF sobre matemáticas aplicadas. Sociedad de matemáticas industriales y aplicadas. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
• Vazirani, Vijay (2012), Una definición mejorada de flores y una prueba más simple del algoritmo de coincidencia MV , CoRR abs/1210.4594, arXiv : 1210.4594 , Bibcode :2012arXiv1210.4594V.