En informática y teoría de grafos , el problema de correspondencia de peso máximo es el problema de encontrar, en un grafo ponderado , una correspondencia en la que se maximice la suma de pesos.
Un caso especial de esto es el problema de asignación , en el que la entrada está restringida a ser un grafo bipartito y la correspondencia está restringida a tener la cardinalidad de la partición más pequeña de las dos. Otro caso especial es el problema de encontrar una correspondencia de cardinalidad máxima en un grafo no ponderado: esto corresponde al caso en el que todos los pesos de las aristas son iguales.
Existe un algoritmo de tiempo para encontrar una correspondencia máxima o una correspondencia de peso máxima en un grafo 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 aristas bidireccionales . También se puede utilizar una generalización de la misma técnica para encontrar conjuntos independientes máximos en grafos sin garras .
Existen algoritmos más elaborados, que han sido revisados por Duan y Pettie [1] (véase la Tabla III). Su trabajo propone un algoritmo de aproximación para el problema de correspondencia de peso máximo, que se ejecuta en tiempo lineal para cualquier límite de error fijo.
