Тема: Максимальное паросочетание в произвольном графе
Недавно на сайте появилась статья о матрице Татта. Насколько я знаю, при помощи такого рандомизированного алгоритма можно не только проверять, существует ли полное паросочетание, а еще и находить размер максимального паросочетания, который равен рангу этой матрицы.