TOPICS
Search

Three-Dimensional Matching Problem

The three-dimensional matching problem asks, for disjoint sets W, X, and Y of equal cardinality q and a subset M subset= W×X×Y, whether there is a subset M^' subset= M of cardinality q in which no two triples agree in any coordinate.

The problem is NP-complete (Karp 1972). It generalizes matching in bipartite graphs from pairs to triples.

See also

Bipartite Graph, Perfect Matching

Explore with Wolfram|Alpha

References

Karp, R. M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972 (Ed. R. E. Miller and J. W. Thatcher). New York: Plenum, pp. 85-103, 1972. https://doi.org/10.1007/978-1-4684-2001-2_9.

Cite this as:

Weisstein, Eric W. "Three-Dimensional Matching Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Three-DimensionalMatchingProblem.html

Subject classifications