Algorithm MRST (McCuaig, Robertson, Seymour, Thomas)

This algorithm recognizes bipartite pfaffian graphs efficiently in $O(nm^3)$.

As this algorithm does not yet have a specific name, we named this algorithm using the initials of its creators (McCuaig, Robertson, Seymour, Thomas) to facilitate the reference of this algorithm in my final paper.

This algorithm was written together with the final paper for the completion of the bachelor's degree in computer science at the Intituto Federal do Norte de Minas Gerais (IFNMG).

After clonning the repository, and installed the C++ Boost library, just type make to execute.

References

McCuaig, W. (2004). Pólya’s permanent problem. The electronic journal of combinatorics, pp. R79–R79.
Robertson, N.; Seymour, P. D. & Thomas, R. (1999). Permanents, pfaffian orientations, and even directed circuits. Annals of Mathematics, 150(3):929–975.