En informática y teoría de grafos , el problema de coincidencia de pesos máximos es el problema de encontrar, en un gráfico ponderado , una coincidencia en la que se maximice la suma de pesos.
Un caso especial es el problema de asignación , en el que la entrada está restringida a ser un gráfico bipartito y la coincidencia está restringida a tener cardinalidad en la de la menor de las dos particiones. Otro caso especial es el problema de encontrar una coincidencia de cardinalidad máxima en un gráfico no ponderado: esto corresponde al caso en el que todos los pesos de los bordes son iguales.
Existe un algoritmo de tiempo para encontrar una coincidencia máxima o una coincidencia de peso máximo 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 aristas 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 que han sido 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.
