Certain NP-complete matching problems (Q794163)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Certain NP-complete matching problems |
scientific article; zbMATH DE number 3858408
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Certain NP-complete matching problems |
scientific article; zbMATH DE number 3858408 |
Statements
Certain NP-complete matching problems (English)
0 references
1984
0 references
A matching problem, which we call 3DMS, is considered and is shown to be NP-complete. From this result there follows directly the NP-completeness of the disjoint matchings decision problem. In addition, the NP- completeness of kDMS \((k>3)\) is established. From this there follow p(k)- 2 other NP-complete matching problems, where p(k) is the cardinality of the set of partitions of the integer k.
0 references
NP-completeness
0 references
disjoint matchings decision problem
0 references
NP-complete matching problems
0 references
