En informática , el problema de correspondencia de pesos máximos es el problema de encontrar, en un gráfico ponderado , una correspondencia en la que se maximice la suma de pesos.
Un caso especial es el problema de asignación , en el que la entrada se restringe a un gráfico bipartito . Otro caso especial es el problema de encontrar una coincidencia máxima de cardinalidad en un gráfico no ponderado: esto corresponde al caso en el que todos los pesos de los bordes son iguales.
Algoritmos
Hay un algoritmo de tiempo para encontrar una coincidencia máxima o una coincidencia de peso máxima en un gráfico que no es bipartito; se debe a Jack Edmonds , se llama método de caminos, árboles y flores o simplemente algoritmo de Edmonds , y utiliza bordes bidireccionales . También se puede utilizar una generalización de la misma técnica para encontrar conjuntos independientes máximos en gráficos sin garras .
Existen algoritmos más elaborados y son revisados por Duan y Pettie [1] (ver Tabla III). Su trabajo propone un algoritmo de aproximación para el problema de coincidencia de peso máximo, que se ejecuta en tiempo lineal para cualquier límite de error fijo.
Referencias
- ^ Duan, Ran; Pettie, Seth (1 de enero de 2014). "Aproximación de tiempo lineal para la máxima coincidencia de peso" (PDF) . Revista de la ACM . 61 : 1-23. doi : 10.1145 / 2529989 .