http://dbpedia.org/ontology/abstract
|
三维匹配问题(3DM)是六个经典NP完全问题之一,是经典的“”的推广,“婚姻问题”的提法是:有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格,问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚? 在三维匹配问题中,可以用集合,和对应于“三个”不同的性别,属于。用集合M中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决,而3DM是NP完全的。
, Na disciplina matemática de teoria dos gra … Na disciplina matemática de teoria dos grafos, um acoplamento tridimensional é uma generalização do acoplamento bipartido (mais conhecido como acoplamento bidimensional) para hipergrafos triuniformes. Encontrar o maior acoplamento tridimensional é um problema NP-difícil bem conhecido na Teoria da Complexidade computacional.o na Teoria da Complexidade computacional.
, In the mathematical discipline of graph th … In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (instead of edges containing 2 vertices in a usual graph). 3-dimensional matching, often abbreviated as 3DM, is also the name of a well-known computational problem: finding a largest 3-dimensional matching in a given hypergraph. 3DM is one of the first problems that were proved to be NP-hard.t problems that were proved to be NP-hard.
, En mathématiques, et notamment en théorie … En mathématiques, et notamment en théorie des graphes, un appariement à 3 dimensions (en anglais : 3-dimensional matching) est une généralisation du couplage (aussi appelé appariement en dimension 2 ) à une situation ternaire qui, techniquement, est celle des hypergraphes dits 3-uniformes. Trouver un appariement à 3 dimensions de taille maximum est un problème NP-difficile bien connu en théorie de la complexité informatique. en théorie de la complexité informatique.
|
http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/3-dimensional-matching.svg?width=300 +
|
http://dbpedia.org/ontology/wikiPageExternalLink
|
https://jsfiddle.net/Lamik/6z4agLue/embedded/result/ +
, http://www.nada.kth.se/~viggo/wwwcompendium/node143.html +
|
http://dbpedia.org/ontology/wikiPageID
|
22261908
|
http://dbpedia.org/ontology/wikiPageLength
|
13052
|
http://dbpedia.org/ontology/wikiPageRevisionID
|
1102258938
|
http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/List_of_NP-complete_problems +
, http://dbpedia.org/resource/Karp%27s_21_NP-complete_problems +
, http://dbpedia.org/resource/Hypergraph +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Category:Combinatorics +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Set_packing +
, http://dbpedia.org/resource/APX-complete +
, http://dbpedia.org/resource/Category:NP-complete_problems +
, http://dbpedia.org/resource/Category:Matching_%28graph_theory%29 +
, http://dbpedia.org/resource/Approximation_algorithm +
, http://dbpedia.org/resource/Exact_cover +
, http://dbpedia.org/resource/Springer_Science%2BBusiness_Media +
, http://dbpedia.org/resource/File:3-dimensional-matching.svg +
, http://dbpedia.org/resource/Bipartite_matching +
, http://dbpedia.org/resource/Matching_%28graph_theory%29 +
, http://dbpedia.org/resource/Massively_parallel +
, http://dbpedia.org/resource/Boolean_satisfiability_problem +
, http://dbpedia.org/resource/Rainbow-independent_set +
, http://dbpedia.org/resource/Mathematical +
, http://dbpedia.org/resource/NP-hard +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/Hopcroft%E2%80%93Karp_algorithm +
, http://dbpedia.org/resource/Dover_Publications +
, http://dbpedia.org/resource/Bipartite_graph +
, http://dbpedia.org/resource/Optimization_problem +
|
http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Reflist +
|
http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Matching_%28graph_theory%29 +
, http://dbpedia.org/resource/Category:Combinatorics +
, http://dbpedia.org/resource/Category:NP-complete_problems +
|
http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Generalization +
|
http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/3-dimensional_matching?oldid=1102258938&ns=0 +
|
http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/3-dimensional-matching.svg +
|
http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/3-dimensional_matching +
|
owl:sameAs |
http://www.wikidata.org/entity/Q10866593 +
, http://fa.dbpedia.org/resource/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%AA%D8%B7%D8%A7%D8%A8%D9%82_%D8%B3%D9%87%E2%80%8C%D8%A8%D8%B9%D8%AF%DB%8C +
, http://rdf.freebase.com/ns/m.05q79w5 +
, https://global.dbpedia.org/id/9x8D +
, http://fr.dbpedia.org/resource/Appariement_%C3%A0_3_dimensions +
, http://dbpedia.org/resource/3-dimensional_matching +
, http://pt.dbpedia.org/resource/Acoplamento_tridimensional +
, http://yago-knowledge.org/resource/3-dimensional_matching +
, http://zh.dbpedia.org/resource/%E4%B8%89%E7%BB%B4%E5%8C%B9%E9%85%8D%E9%97%AE%E9%A2%98 +
|
rdf:type |
http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Difficulty114408086 +
, http://dbpedia.org/class/yago/Condition113920835 +
, http://dbpedia.org/class/yago/Attribute100024264 +
, http://dbpedia.org/class/yago/State100024720 +
, http://dbpedia.org/class/yago/Problem114410605 +
, http://dbpedia.org/class/yago/WikicatNP-completeProblems +
|
rdfs:comment |
In the mathematical discipline of graph th … In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (instead of edges containing 2 vertices in a usual graph). 3-dimensional matching, often abbreviated as 3DM, is also the name of a well-known computational problem: finding a largest 3-dimensional matching in a given hypergraph. 3DM is one of the first problems that were proved to be NP-hard.t problems that were proved to be NP-hard.
, 三维匹配问题(3DM)是六个经典NP完全问题之一,是经典的“”的推广,“婚姻问题”的提法是:有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格,问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚? 在三维匹配问题中,可以用集合,和对应于“三个”不同的性别,属于。用集合M中的每一个三元组对应一对这三个成员都能接受的“三方婚姻”。普通的婚姻问题可以在多项式时间内解决,而3DM是NP完全的。
, En mathématiques, et notamment en théorie … En mathématiques, et notamment en théorie des graphes, un appariement à 3 dimensions (en anglais : 3-dimensional matching) est une généralisation du couplage (aussi appelé appariement en dimension 2 ) à une situation ternaire qui, techniquement, est celle des hypergraphes dits 3-uniformes. Trouver un appariement à 3 dimensions de taille maximum est un problème NP-difficile bien connu en théorie de la complexité informatique. en théorie de la complexité informatique.
, Na disciplina matemática de teoria dos gra … Na disciplina matemática de teoria dos grafos, um acoplamento tridimensional é uma generalização do acoplamento bipartido (mais conhecido como acoplamento bidimensional) para hipergrafos triuniformes. Encontrar o maior acoplamento tridimensional é um problema NP-difícil bem conhecido na Teoria da Complexidade computacional.o na Teoria da Complexidade computacional.
|
rdfs:label |
Acoplamento tridimensional
, 3-dimensional matching
, Appariement à 3 dimensions
, 三维匹配问题
|