Los algoritmos más conocidos para la Coincidencia máxima de cardinalidad en gráficos generales son: [1] para gráficos dispersos (complejidad de tiempo [matemática] O (| E | * \ sqrt {| V |}) [/ matemática]) y [2] para gráficos densos (complejidad de tiempo [matemáticas] O (| V | ^ {2.37}) [/ matemáticas]). [3] para gráficos bipartitos dispersos (complejidad de tiempo [matemática] O (| E | * \ sqrt {| V |}) [/ matemática]) que es mucho más simple que [1].
PS: Suponga que el Gráfico G = (V, E)
[1] Micali, Silvio y Vijay V. Vazirani. “Un algoritmo O (v | v | c | E |) para encontrar la coincidencia máxima en gráficos generales”. Fundamentos de la informática, 1980., 21º Simposio anual sobre. IEEE, 1980.
[2] Mucha, Marcin y Piotr Sankowski. “Emparejamientos máximos por eliminación gaussiana”. Fundamentos de Informática, 2004. Actas. 45º Simposio anual de IEEE sobre. IEEE, 2004.
[3] Hopcroft, John E. y Richard M. Karp. “Un algoritmo n ^ 5/2 para coincidencias máximas en gráficos bipartitos”. SIAM Journal on Computing 2.4 (1973): 225-231.
- Cómo probar la corrección del problema de cambio de moneda usando DP y poda
- ¿Cuáles son algunas de las preguntas famosas al calcular los caminos más cortos (gráficos) usando Dijkstra's, DAG y Bellman-Ford?
- ¿La informática es solo sobre programación y algoritmos?
- ¿Qué tan útil es el algoritmo genético?
- ¿Cuál fue el algoritmo utilizado por AlphaGo para ganar el juego de Go contra el campeón europeo de Go humano?
