Statements (28)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
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 |
theoretical computer science
combinatorics |
| gptkbp:firstDescribed |
gptkb:Richard_M._Karp
1972 |
| gptkbp:generalizes |
bipartite matching
|
| gptkbp:hardness |
APX-hard
|
| https://www.w3.org/2000/01/rdf-schema#label |
3-dimensional matching
|
| 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
|
| gptkbp:bfsLayer |
7
|