Maximum Matchings in the n-Dimensional Cube |
| |
Authors: | Tarakanov V. E. |
| |
Affiliation: | (1) V. A. Steklov Mathematics Institute, Russian Academy of Sciences, Russia |
| |
Abstract: | The problem of efficient computation of maximum matchings in the n-dimensional cube, which is applied in coding theory, is solved. For an odd n, such a matching can be found by the method given in our Theorem 2. This method is based on the explicit construction (Theorem 1) of the maps of the vertex set that induce largest matchings in any bipartite subgraph of the n-dimensional cube for any n. |
| |
Keywords: | maximum matchings n-dimensional cube bipartite graphs Hamming distance |
本文献已被 SpringerLink 等数据库收录! |