Esiste un algoritmo polinomiale per trovare la corrispondenza perfetta ponderata massima in un grafico generale?

Question

Vedo che lo Blossom algorithm può essere utilizzato per risolvere la versione non ponderata di questo problema e so che questo problema può anche essere ridotto a un problema di LP (ma con un numero esponenziale di vincoli). C'è un modo per risolverlo in tempo polinomiale?

Answer 1

Sì, l'algoritmo Blossom per calcolare le corrispondenze generali massime non pesate può essere utilizzato in un algoritmo primale-duale per le corrispondenze generali ponderate massime (questa è una tecnica generale, l'algoritmo ungherese è l'equivalente bipartito). C'è un'implementazione chiamata Blossom V dovuta a Vladimir Kolmogorov.