| Property |
Value |
| dbo:abstract
|
- L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et (en), 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)
- L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et (en), 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)
|
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12225 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
| |
| prop-fr:auteur
|
- Yann Strozecki (fr)
- Yann Strozecki (fr)
|
| prop-fr:consultéLe
| |
| prop-fr:jour
| |
| prop-fr:mois
|
- décembre (fr)
- décembre (fr)
|
| prop-fr:texte
|
- Harold N. Temperley (fr)
- Harold N. Temperley (fr)
|
| prop-fr:titre
|
- Comptage des couplages parfaits dans un graphe planaire (fr)
- Comptage des couplages parfaits dans un graphe planaire (fr)
|
| prop-fr:trad
|
- Harold Neville Vazeille Temperley (fr)
- Harold Neville Vazeille Temperley (fr)
|
| prop-fr:url
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et (en), 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)
- L'algorithme FKT, nommé ainsi d'après Michael Fisher, (en) et (en), 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)
|
| rdfs:label
|
- Algorithme FKT (fr)
- FKT algorithm (en)
- Алгоритм FKT (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
