Talk:FKT algorithm

Suggestions for Improvement

Here are suggestions of ways to improve this article:

• Improve the History section. A good reference to use is one that I have already cited in the History and Application sections.

Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2010). Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. Las Vegas, NV, USA: IEEE. {{cite conference}}: External link in |conferenceurl= (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help)

• Add to The Algorithm section a gif showing how steps 1 - 6 work. Pictures similar to those from the external link (provided below) would work well.

Presentation by Ashley Montanaro about the FKT algorithm

• Add a Proof of Correctness section that...proves why the algorithm is correct. A good starting reference for this is (also) the external link.

Presentation by Ashley Montanaro about the FKT algorithm

• Possibly add to the Generalization section content from the following paper.

Little, C. H. C. (1974), "An extension of Kasteleyn's method of enumerating the 1-factors of planar graphs", in Holton, D. (ed.), Proc. 2nd Australian Conf. Combinatorial Mathematics, Lecture Notes in Mathematics, vol. 403, Springer-Verlag, pp. 63–72.

Bender2k14 (talk) 12:47, 23 December 2010 (UTC)