Algoritmo de Hopcroft-Karp

Algoritmo para máxima coincidencia de cardinalidad

En informática , el algoritmo Hopcroft-Karp (a veces llamado con mayor 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 no hay dos bordes que compartan un punto final. Se ejecuta en el tiempo en el peor de los casos , donde es un conjunto de aristas en el gráfico, es un conjunto de vértices del gráfico, y se supone que . En el caso de gráficos densos, el límite de tiempo se vuelve , 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] Como en métodos anteriores de coincidencia, como el algoritmo húngaro y el trabajo de Edmonds (1965), el algoritmo Hopcroft-Karp aumenta repetidamente el tamaño de una coincidencia parcial al encontrar caminos de aumento . Estas rutas son secuencias de aristas del gráfico, que alternan entre aristas en la coincidencia y aristas fuera de la coincidencia parcial, y donde las aristas inicial y final no están en la coincidencia parcial. Encontrar una ruta de aumento nos permite incrementar el tamaño de la coincidencia parcial, simplemente alternando los bordes de la ruta de aumento (poniendo en la coincidencia parcial aquellos que no lo eran, y viceversa). Los algoritmos más simples para el emparejamiento bipartito, como el algoritmo Ford-Fulkerson , encuentran una ruta de aumento por iteración: el algoritmo Hopcroft-Karp, en cambio, encuentra un conjunto máximo de rutas de aumento más cortas, para garantizar que solo se necesiten iteraciones en lugar de iteraciones. Se puede lograr el mismo rendimiento para encontrar coincidencias de cardinalidad máxima en gráficos 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 Hopcroft-Karp puede verse como un caso especial del algoritmo de Dinic para el problema de flujo máximo . ^[5]

Caminos de aumento

Un vértice que no es el punto final de una arista en alguna coincidencia parcial se llama vértice libre . El concepto básico en el que se basa el algoritmo es el de una ruta aumentada , una ruta que comienza en un vértice libre, termina en un vértice libre y alterna entre aristas coincidentes y no coincidentes dentro de la ruta. De esta definición se deduce que, excepto los puntos finales, todos los demás vértices (si los hay) en la ruta aumentada deben ser vértices no libres. Un camino aumentado podría consistir en sólo dos vértices (ambos libres) y un único borde inigualable 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 el tamaño . Por lo tanto, al encontrar caminos 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 hay una coincidencia óptima. Debido a que y son ambos coincidentes, cada vértice tiene un grado como máximo de 2 pulg . Por lo tanto, debe formar una colección de ciclos disjuntos, de caminos con un número igual de aristas coincidentes y no coincidentes en , de caminos aumentados para y de caminos aumentados para ; pero esto último es imposible porque es óptimo. Ahora, los ciclos y los caminos con igual número 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 aumentados para in . Por lo tanto, siempre que exista una coincidencia mayor que la coincidencia actual , también debe existir una ruta de aumento. Si no se puede encontrar una ruta de aumento, un algoritmo puede terminar de forma 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 coincidencia 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 las terminales del flujo. Es posible transformar el problema de coincidencia bipartito en una instancia de flujo máximo, de modo que los caminos alternos del problema de coincidencia se conviertan en caminos crecientes 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 hasta el sumidero; y deje que los bordes tengan capacidad unitaria. ^[6] Una generalización de la técnica utilizada en el algoritmo 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 separados por vértices

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

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

Con más detalle, sean y los dos conjuntos en la bipartición de y deje que la coincidencia de a en cualquier momento se represente 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 gráfico en capas. Los vértices libres se utilizan como vértices iniciales de esta búsqueda y forman la primera capa de la partición. En el primer nivel de 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, los bordes atravesados ​​deben alternar entre coincidentes y no coincidentes. Es decir, cuando se buscan sucesores desde un vértice en , solo se pueden atravesar los bordes no coincidentes, mientras que desde un vértice en solo se pueden atravesar los bordes coincidentes. La búsqueda termina en la primera capa donde se alcanzan uno o más vértices libres. ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle V}$
• Todos los vértices libres en una capa se recopilan en un conjunto . Es decir, se coloca un vértice si y sólo 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 de longitud disjuntas de vértices . ( 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 rutas de este tipo, lo cual sería más difícil de hacer. Afortunadamente, aquí es suficiente encontrar un conjunto máximo de rutas). Este conjunto puede ser calculado mediante búsqueda en profundidad (DFS) desde los vértices libres en , utilizando la primera capa de amplitud para guiar la búsqueda: el DFS solo puede seguir bordes que conducen a un vértice no utilizado en la capa anterior y rutas en el DFS El árbol debe alternar entre bordes coincidentes y no coincidentes. Una vez que se encuentra una ruta de aumento que involucra uno de los vértices en , el DFS continúa desde el siguiente vértice inicial. Cualquier vértice encontrado durante el DFS se puede marcar inmediatamente como usado, ya que si no hay una ruta desde él hasta el punto actual del DFS, entonces ese vértice no se puede usar para llegar a ningún otro punto del DFS. Esto garantiza el tiempo de ejecución del DFS. También es posible trabajar en el otro sentido, desde los vértices libres en hacia los en , 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 encontrados de esta manera sirve para ampliar . ${\displaystyle M}$

El algoritmo termina cuando no se encuentran más rutas de aumento en la primera 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. De este modo, se podrá implementar una sola fase a tiempo. Por tanto, las primeras fases, en un gráfico con vértices y aristas, toman tiempo . ${\displaystyle O(|E|)}$ ${\displaystyle {\sqrt {|V|}}}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$ ${\displaystyle O(|E|{\sqrt {|V|}})}$

Cada fase aumenta 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 eventual y del emparejamiento parcial M encontrado por las fases iniciales forma una colección de caminos de aumento disjuntos de vértices y ciclos alternos. Si cada una de las rutas de esta colección tiene una longitud de al menos , puede haber como máximo rutas en la colección y el tamaño de la coincidencia óptima puede diferir del tamaño de como máximo los bordes. Dado que cada fase del algoritmo aumenta el tamaño de la coincidencia en al menos uno, puede haber como máximo fases adicionales antes de que finalice el algoritmo. ${\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, en el peor de los casos tarda un tiempo total . ${\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 de lo que indica el análisis del peor de los casos. Por ejemplo, en el caso promedio de gráficos aleatorios bipartitos dispersos , Bast et al. (2006) (mejorando un resultado anterior de Motwani 1994) mostraron que con alta probabilidad todos los emparejamientos no óptimos tienen caminos crecientes de longitud logarítmica . Como consecuencia, para estos gráficos, el algoritmo Hopcroft-Karp toma fases y tiempo total. ${\displaystyle O(\log |V|)}$ ${\displaystyle O(|E|\log |V|)}$

Comparación con otros algoritmos de coincidencia bipartita

Para gráficos dispersos , el algoritmo Hopcroft-Karp sigue teniendo el peor rendimiento mejor conocido, pero para gráficos densos ( ) un algoritmo más reciente de Alt et al. (1991) logra un límite temporal ligeramente mejor . Su algoritmo se basa en el uso de un algoritmo de flujo máximo de reetiquetación push 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 por estrategias más simples de primero en amplitud y primero en profundidad para encontrar caminos de aumento, y por técnicas de reetiquetado por empuje. . ^[7]

Gráficos no bipartitos

La misma idea de encontrar un conjunto máximo de caminos de aumento más cortos funciona también para encontrar coincidencias de cardinalidad máxima en gráficos no bipartitos y, por las mismas razones, los algoritmos basados ​​en esta idea toman fases. Sin embargo, para gráficos no bipartitos, la tarea de encontrar los caminos crecientes 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 dio como resultado un algoritmo de coincidencia no bipartito con el mismo límite de tiempo que el algoritmo Hopcroft-Karp para gráficos bipartitos. La técnica de Micali-Vazirani es compleja y sus autores no aportaron 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 de Micali-Vazirani. ^[9] ${\displaystyle O({\sqrt {|V|}})}$

Pseudocódigo

/* GRAMO = U ∪ V ∪ {NIL} 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 que Vacío (Q) = falso u := Sacar de la cola(Q) si Dist[u] < Dist[NIL] entonces  para cada v en Adj[u] haga  si Dist[Pair_V[v]] = ∞ entonces Dist[Par_V[v]] := Dist[u] + 1 Poner en cola(Q, Pair_V[v]) devolver Dist[NIL] ≠ ∞la función DFS(u) es  si u ≠ NIL entonces  para cada v en Adj[u] haga  si Dist[Pair_V[v]] = Dist[u] + 1 entonces  si DFS(Pair_V[v]) = verdadero entonces Par_V[v] := u Par_U[u] := v devolver verdadero Dist[u] := ∞ devolver falso devolver verdaderola función Hopcroft-Karp es  para cada u en U do Par_U[u] := NULO para cada v en V hacer Par_V[v] := NULO coincidencia := 0 mientras que BFS() = verdadero hazlo  para cada u en U hazlo  si Pair_U[u] = NIL entonces  si DFS(u) = verdadero entonces coincidencia := coincidencia + 1 coincidencia de retorno

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 gráfico estén divididos en U y V, y considere una coincidencia parcial, como lo indican las tablas Pair_U y Pair_V que contienen el único vértice con el que coincide cada vértice de U y V, o NIL para vértices no coincidentes. La idea clave es agregar dos vértices ficticios a cada lado del gráfico: 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) desde uDummy hasta vDummy entonces podemos obtener los caminos 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 gráfico es bipartito, estos caminos siempre alternan entre vértices en U y vértices en V, y requerimos en nuestro BFS que al pasar de V a U, siempre seleccionamos un borde coincidente. Si alcanzamos un vértice de V no coincidente, terminamos en vDummy y termina la búsqueda de rutas en el BFS. Para resumir, el BFS comienza en vértices no coincidentes en U, va a todos sus vecinos en V, si todos coinciden entonces regresa a los vértices en U con los que coinciden todos estos vértices (y que no fueron visitados antes), entonces va a todos los vecinos de estos vértices, etc., hasta que uno de los vértices alcanzados en V no coincida.

Observe en particular que BFS marca los nodos no coincidentes de U con distancia 0, luego incrementa la distancia cada vez que regresa a U. Esto garantiza que los caminos considerados en el BFS sean de longitud mínima para conectar vértices no coincidentes de U con vértices no coincidentes de V mientras siempre retrocede de V a U en los bordes que actualmente forman parte de la coincidencia. En particular, al vértice NIL especial, que corresponde a vDummy, se le asigna una distancia finita, por lo que la función BFS devuelve verdadero 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 utilizando una búsqueda en profundidad (DFS). Tenga en cuenta que cada vértice en V en dicha ruta, excepto el último, coincide actualmente. Entonces podemos explorar con el DFS, asegurándonos de que los caminos que seguimos corresponden a las distancias calculadas en el BFS. Actualizamos a lo largo de cada ruta 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: ya que esta es una ruta de aumento (la primera y los últimos bordes del camino no eran parte de la coincidencia, y el camino alternaba entre bordes coincidentes y no coincidentes), 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.

Tenga en cuenta que el código garantiza que todas las rutas de aumento que consideramos sean vértices disjuntos. De hecho, después de hacer la diferencia simétrica para un camino, ninguno de sus vértices podría ser considerado nuevamente en el DFS, simplemente porque el 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 es gracias a las siguientes líneas:

Dist[u] = ∞falso retorno

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 vuelvan a visitar.

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 indica como NIL en el pseudocódigo anterior.

Ver también

• Coincidencia de cardinalidad máxima , el problema resuelto por el algoritmo y su generalización a gráficos 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 encontrar el flujo 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 coincidencia de cardinalidad bipartita, págs.
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 redes: teoría, algoritmos y aplicaciones , Prentice-Hall.
• Alt, H.; Blum, N.; Mehlhorn, K .; Paul, M. (1991), "Cálculo de una coincidencia de cardinalidad máxima en un gráfico bipartito en el tiempo ", Cartas de procesamiento de información , 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 coincidencias perfectas en hipergrafías bipartitas", 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 coincidencia son rápidos en gráficos aleatorios dispersos", Teoría de sistemas informáticos , 39 (1): 3–14, CiteSeerX  10.1.1.395.6643 , doi :10.1007/s00224-005-1254-y , SEÑOR  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ánica. Según lo citado por Setúbal (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 , Ph.D. tesis, Universidad Brunel. Según lo citado por Setúbal (1996).
• Dinitz, Yefim (2006), "Algoritmo de Dinitz: la versión original y la versión par", en Goldreich, Oded ; Rosenberg, Arnold L .; Selman, Alan L. (eds.), Informática teórica: ensayos en memoria de Shimon Even (PDF) , Apuntes de conferencias sobre informática, vol. 3895, Berlín y Heidelberg: Springer, págs. 218–240, doi :10.1007/11685654_10, ISBN 978-3-540-32880-3.
• Edmonds, Jack (1965), "Senderos, árboles y flores", Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , MR  0177907, S2CID  18909734.
• Gabow, Harold N. (2017), "El enfoque de coincidencia ponderada para la máxima coincidencia de 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 escalado más rápidos para problemas generales de coincidencia de gráficos", 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 coincidencias máximas en gráficos bipartitos", SIAM Journal on Computing , 2 (4): 225–231, doi :10.1137/0202019. Anunciado previamente 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, aplicada al problema de los representantes", Problems in Cybernetics , 5 : 66–70. Anunciado previamente 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. 21º Simposio IEEE. Fundamentos de la informática , 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 coincidencias 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-216. Según lo citado por Setúbal (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ática Industrial y Aplicada. 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.