Complexity of a 3-dimensional assignment problem |
| |
| Authors: | AM Frieze |
| |
| Institution: | Department of Computer Science & Statistics, Queen Mary College, University of London, London El 4NS, United Kingdom |
| |
| Abstract: | We show that a certain 3-dimensional assignment problem is NP-complete. To do this we show that the following problem is NP-complete: given bipartite graphs G1, G2 with the same sets of vertices, do there exist perfect matchings M1, M2 of G1, G2 respectively such that M1 ∩ M2 =Ø? |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
