Přizpůsobení maximální hmotnosti - Maximum weight matching

v počítačová věda, maximální shoda hmotnosti problém je problém hledání, v a vážený graf, a vhodný ve kterém je součet vah maximalizován.

Zvláštním případem je problém s přiřazením, ve kterém je vstup omezen na a bipartitní graf. Dalším zvláštním případem je problém najít a maximální shoda mohutnosti na neváženém grafu: to odpovídá případu, kdy jsou všechny okrajové hmotnosti stejné.

Algoritmy

Tady je ${displaystyle O (V ^ {2} E)}$ časový algoritmus k nalezení maximální shody nebo maximální shody hmotnosti v grafu, který není bipartitní; je to kvůli Jack Edmonds, se nazývá cesty, stromy a květiny metoda nebo jednoduše Edmondsův algoritmus a použití obousměrné hrany. K nalezení lze také použít zevšeobecnění stejné techniky maximální počet nezávislých sad v grafy bez drápů.

Existují propracovanější algoritmy, které přezkoumávají Duan a Pettie^[1] (viz tabulka III). Jejich práce navrhuje aproximační algoritmus pro problém s přizpůsobením maximální hmotnosti, který běží v lineárním čase pro jakoukoli pevnou vázanou chybu.

Reference