Grafové párovanie má nový algoritmus s takmer kvadratickým časom
Nový preprint rieši základnú úlohu grafového párovania v korelovaných náhodných grafoch. Autori navrhujú algoritmus založený na lokálnych testoch stromovej korelácie, ktorý má dosiahnuť takmer presnú obnovu pri takmer kvadratickej zložitosti v režime, kde boli skoršie metódy výrazne pomalšie.