FKT algorithm (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (en) L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et Harold N. Temperley, compte le nombre de couplages parfaits dans un graphe planaire, et ceci en temps polynomial. Le même dénombrement est #P-complet pour les graphes généraux. Pour les couplages qui ne sont pas nécessairement parfaits, leur dénombrement reste #P-complet même pour les graphes planaires. L'idée clé de l'algorithme FKT est de convertir le problème en le calcul du pfaffien d'une matrice antisymétrique obtenue à partir d'un plongement planaire du graphe. Le pfaffien de cette matrice est ensuite calculé efficacement à l'aide d'algorithmes standards pour les déterminants . (fr) 그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다. (ko) FKT (назван по именам Фишера, и ) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Pfaffian_orientation_via_FKT_algorithm_example.gif?width=300 |
| dbo:wikiPageExternalLink | https://digitalcollections.anu.edu.au/bitstream/1885/49338/2/02whole.pdf |
| dbo:wikiPageID | 30159370 (xsd:integer) |
| dbo:wikiPageLength | 12668 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1051899726 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Determinant dbr:Hosoya_index dbr:Perfect_matching dbr:Regular_graph dbr:Kuratowski's_theorem dbc:Planar_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Matching_(graph_theory) dbr:Orientation_(graph_theory) dbr:Tutte_matrix dbr:Glossary_of_graph_theory dbr:Harold_Neville_Vazeille_Temperley dbr:P_(complexity) dbr:Parity_of_a_permutation dbr:Pfaffian dbr:Sharp-P dbr:Spanning_tree dbc:Graph_algorithms dbr:Lattice_graph dbr:Adjacency_matrix dbr:Dual_graph dbr:Partition_function_(statistical_mechanics) dbr:Diatomic_molecule dbr:Dimer_(chemistry) dbr:Graph_embedding dbr:H2O dbr:Counting_problem_(complexity) dbr:Statistical_mechanics dbr:Arthur_Cayley dbr:Chemistry dbr:Holographic_algorithm dbr:Homeomorphism_(graph_theory) dbr:Domino_tiling dbr:Boolean_satisfiability_problem dbr:Pieter_Kasteleyn dbr:Planar_graph dbr:If_and_only_if dbr:Michael_Fisher dbr:Skew-symmetric_matrix dbr:Vijay_Vazirani dbr:FP_(complexity) dbr:Sharp-P-complete dbr:Pfaffian_orientation dbr:Finite_graph dbr:File:Pfaffian_orientation_via_FKT_algorithm_example.gif dbr:Matchgates |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Planar_graphs dbc:Graph_algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Graph107000195 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:VisualCommunication106873252 yago:WikicatPlanarGraphs |
| rdfs:comment | 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. (en) L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et Harold N. Temperley, compte le nombre de couplages parfaits dans un graphe planaire, et ceci en temps polynomial. Le même dénombrement est #P-complet pour les graphes généraux. Pour les couplages qui ne sont pas nécessairement parfaits, leur dénombrement reste #P-complet même pour les graphes planaires. L'idée clé de l'algorithme FKT est de convertir le problème en le calcul du pfaffien d'une matrice antisymétrique obtenue à partir d'un plongement planaire du graphe. Le pfaffien de cette matrice est ensuite calculé efficacement à l'aide d'algorithmes standards pour les déterminants . (fr) 그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다. (ko) FKT (назван по именам Фишера, и ) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя. (ru) |
| rdfs:label | FKT algorithm (en) Algorithme FKT (fr) 파프 방향 (ko) Алгоритм FKT (ru) |
| owl:sameAs | freebase:FKT algorithm yago-res:FKT algorithm wikidata:FKT algorithm dbpedia-fa:FKT algorithm dbpedia-fr:FKT algorithm dbpedia-ko:FKT algorithm dbpedia-ru:FKT algorithm dbpedia-sr:FKT algorithm https://global.dbpedia.org/id/4jYdj |
| prov:wasDerivedFrom | wikipedia-en:FKT_algorithm?oldid=1051899726&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Pfaffian_orientation_via_FKT_algorithm_example.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:FKT_algorithm |
| is dbo:knownFor of | dbr:Pieter_Kasteleyn dbr:Michael_Fisher |
| is dbo:wikiPageDisambiguates of | dbr:FKT |
| is dbo:wikiPageWikiLink of | dbr:FKT dbr:List_of_graph_theory_topics dbr:Perfect_matching dbr:Computing_the_permanent dbr:Matching_(graph_theory) dbr:Orientation_(graph_theory) dbr:Harold_Neville_Vazeille_Temperley dbr:Pfaffian dbr:Holographic_algorithm dbr:Pieter_Kasteleyn dbr:Michael_Fisher dbr:Tutte_polynomial dbr:Pfaffian_orientation |
| is dbp:knownFor of | dbr:Pieter_Kasteleyn |
| is foaf:primaryTopic of | wikipedia-en:FKT_algorithm |
