FKT algorithm
http://dbpedia.org/resource/FKT_algorithm an entity of type: Abstraction100002137
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.
rdf:langString
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 .
rdf:langString
그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.
rdf:langString
FKT (назван по именам Фишера, и ) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.
rdf:langString
rdf:langString
FKT algorithm
rdf:langString
Algorithme FKT
rdf:langString
파프 방향
rdf:langString
Алгоритм FKT
xsd:integer
30159370
xsd:integer
1051899726
rdf:langString
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.
rdf:langString
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 .
rdf:langString
그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.
rdf:langString
FKT (назван по именам Фишера, и ) — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.
xsd:nonNegativeInteger
12668
