FKT algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, counting them remains #P-complete even for planar graphs. The key idea of the FKT algorithm is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms.
- Comment
- enThe FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, counting them remains #P-complete even for planar graphs. The key idea of the FKT algorithm is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms.
- Depiction
- Has abstract
- enThe FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, counting them remains #P-complete even for planar graphs. The key idea of the FKT algorithm is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms.
- Is primary topic of
- FKT algorithm
- Label
- enFKT algorithm
- Link from a Wikipage to an external page
- digitalcollections.anu.edu.au/bitstream/1885/49338/2/02whole.pdf
- Link from a Wikipage to another Wikipage
- Adjacency matrix
- Arthur Cayley
- Boolean satisfiability problem
- Category:Graph algorithms
- Category:Planar graphs
- Chemistry
- Complete bipartite graph
- Complete graph
- Counting problem (complexity)
- Determinant
- Diatomic molecule
- Dimer (chemistry)
- Domino tiling
- Dual graph
- File:Pfaffian orientation via FKT algorithm example.gif
- Finite graph
- FP (complexity)
- Glossary of graph theory
- Graph embedding
- H2O
- Harold Neville Vazeille Temperley
- Holographic algorithm
- Homeomorphism (graph theory)
- Hosoya index
- If and only if
- Kuratowski's theorem
- Lattice graph
- Matchgates
- Matching (graph theory)
- Michael Fisher
- Orientation (graph theory)
- P (complexity)
- Parity of a permutation
- Partition function (statistical mechanics)
- Perfect matching
- Pfaffian
- Pfaffian orientation
- Pieter Kasteleyn
- Planar graph
- Regular graph
- Sharp-P
- Sharp-P-complete
- Skew-symmetric matrix
- Spanning tree
- Statistical mechanics
- Tutte matrix
- Vijay Vazirani
- SameAs
- 4jYdj
- Algorithme FKT
- FKT algoritam
- FKT algorithm
- m.0g5525
- Q5426031
- Алгоритм FKT
- الگوریتم FKT
- 파프 방향
- Subject
- Category:Graph algorithms
- Category:Planar graphs
- Thumbnail
- WasDerivedFrom
- FKT algorithm?oldid=1051899726&ns=0
- WikiPageLength
- 12668
- Wikipage page ID
- 30159370
- Wikipage revision ID
- 1051899726
- WikiPageUsesTemplate
- Template:Reflist
- Template:Short description
