Count Number of Perfect Matchings in a Planar Graph

Description
<span></span><p dir="ltr"><span><b>The Problem</b></span></p><p dir="ltr"><span>Counting the number of perfect matchings (http://en.wikipedia.org/wiki/Matching_(graph_theory)) in a planar graph is a theoretically interesting task that is of use in holographic algorithms (</span><a href="http://en.wikipedia.org/wiki/Holographic_algorithm"><span>http://en.wikipedia.org/wiki/Holographic_algorithm</span></a><span>) and in certain areas of chemistry and statistical mechanics.</span></p><p dir="ltr"><span><b>The Interface</b></span></p><p dir="ltr"><span>Takes a graph as input. Use Map&lt;String,List&lt;String&gt;&gt;, where strings are node names, and the List&lt;String&gt; is the adjacency list for the node.</span></p><p dir="ltr"><span><b>The Algorithm</b></span></p><span>This is usually handled by the &#160;FKT algorithm (</span><a href="http://en.wikipedia.org/wiki/FKT_algorithm"><span>http://en.wikipedia.org/wiki/FKT_algorithm</span></a><span>). The problem of computing the number of perfect matching in a general graph is hard (#P-complete), this special case is polynomial time. The implementation should check to make sure the graph is planar and return an error if it isn&#8217;t.</span>
Discussion
  • {{comment.username}}
Status
Active
submission(s) pending review
Bounty expires in
Bounty expired
Bounty
50
Tags
(no tags)