Hopcroft–Karp algorithm
Algoritmo que encuentra el mayor emparejamiento posible en un grafo bipartito, es decir, el máximo número de parejas sin elementos repetidos.
- Año
- 1973
- Protagonistas
- John Hopcroft, Richard Karp
- Sección
- Informática
Historia
El algoritmo de Hopcroft-Karp resuelve un problema clásico de la teoría de grafos: dado un grafo bipartito, cuyos vértices se dividen en dos conjuntos de forma que las aristas solo unen elementos de conjuntos distintos, hallar un emparejamiento de máximo tamaño, es decir, el mayor conjunto de aristas en el que ningún vértice aparece dos veces. Es un problema que aparece al asignar tareas a trabajadores, puestos a candidatos o recursos a procesos, y por eso su solución eficiente tiene utilidad práctica en muchos sistemas informáticos.
Antes de este algoritmo ya existían métodos para resolver el problema. El más conocido era el algoritmo húngaro, ideado para la asignación de tareas, y el procedimiento basado en caminos aumentantes, es decir, secuencias de aristas que alternan entre las que ya están en el emparejamiento y las que no, de modo que intercambiar su pertenencia aumenta en una unidad el tamaño del conjunto. Un método sencillo, como el de Ford-Fulkerson, busca un solo camino aumentante en cada iteración, lo que puede exigir muchas iteraciones cuando el grafo es grande.
La idea central de Hopcroft y Karp consiste en buscar en cada fase un conjunto maximal de caminos aumentantes más cortos y aplicarlos todos a la vez. Para ello, cada fase comienza con una búsqueda en anchura desde los vértices libres de un conjunto, que los agrupa en capas según la distancia. Después, una búsqueda en profundidad, guiada por esas capas, localiza caminos disjuntos que llegan a vértices libres del otro conjunto. Como cada fase requiere solo un recorrido en anchura y otro en profundidad, su coste es proporcional al número de aristas, y el número de fases necesarias queda acotado por la raíz cuadrada del número de vértices.
El trabajo fue publicado en 1973 por John Hopcroft y Richard Karp, de forma independiente a los resultados del matemático soviético Alexander Karzanov, que llegó a una idea similar por su cuenta. Por esa razón algunos autores lo llaman algoritmo de Hopcroft-Karp-Karzanov. Su análisis de complejidad mejoró las cotas conocidas hasta entonces para este problema y se convirtió en un modelo de referencia en los textos de algoritmia. Más tarde se observó que puede verse como un caso particular del algoritmo de Dinic para el problema del flujo máximo en redes, que generaliza la misma técnica de capas y caminos cortos a redes arbitrarias.
En el mundo actual el algoritmo sigue siendo una herramienta básica en la enseñanza de la algoritmia y aparece en bibliotecas de software para análisis de grafos, en problemas de asignación y en la planificación de recursos. Su eficacia en grafos dispersos y su comportamiento favorable en grafos aleatorios explican que se siga empleando cuando el tamaño de los datos crece.
Cronología
- 1973John Hopcroft y Richard Karp publican el algoritmo, y Alexander Karzanov llega a resultados similares de forma independiente.
John Hopcroft1939 · Informática
Richard Karp1935 · Informática