|
gptkbp:instanceOf
|
gptkb:theoretical_computer_science
|
|
gptkbp:category
|
NP-complete problems
matching problems
|
|
gptkbp:complexity
|
NP-complete
|
|
gptkbp:decision
|
yes
|
|
gptkbp:estimatedCost
|
yes
|
|
gptkbp:exactAlgorithmKnown
|
no (unless P=NP)
|
|
gptkbp:field
|
gptkb:combinatorics
gptkb:theoretical_computer_science
|
|
gptkbp:firstDescribed
|
gptkb:Richard_M._Karp
1972
|
|
gptkbp:generalizes
|
bipartite matching
|
|
gptkbp:hardness
|
APX-hard
|
|
gptkbp:input
|
set of triples T ⊆ X × Y × Z
three disjoint sets X, Y, Z
|
|
gptkbp:minimumInputSize
|
|X| = |Y| = |Z| = n
|
|
gptkbp:output
|
matching of size n
|
|
gptkbp:relatedTo
|
gptkb:3-SAT
gptkb:matching_(graph_theory)
set packing
|
|
gptkbp:type
|
combinatorial optimization
Is there a matching M ⊆ T such that every element of X, Y, Z appears in exactly one triple in M?
|
|
gptkbp:usedIn
|
gptkb:complexity_theory
algorithm design
approximation algorithms
|
|
gptkbp:bfsParent
|
gptkb:Exact_cover_by_3-sets
gptkb:Exact_Cover_by_3-Sets_(X3C)
gptkb:k-dimensional_matching
gptkb:X3C
|
|
gptkbp:bfsLayer
|
8
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
3-dimensional matching
|