Back to Search
Start Over
Shortening Array Codes and the Perfect 1-Factorization Conjecture.
- Source :
-
IEEE Transactions on Information Theory . Feb2009, Vol. 55 Issue 2, p507-513. 7p. - Publication Year :
- 2009
-
Abstract
- The existence of a perfect 1-factorization of the complete graph with n nodes, namely, Kn, for arbitrary even number n, is a 40-year-old open problem in graph theory. So far, two infinite families of perfect 1-factorizations have been shown to exist, namely, the factorizations of Kp+1 and K2p, where p is an arbitrary prime number (p > 2). It was shown in previous work that finding a perfect 1-factorization of Kn is related to a problem in coding, specifically, it can be reduced to constructing an MDS (Minimum Distance Separable), lowest density array code. In this paper, a new method for shortening arbitrary array codes is introduced. It is then used to derive the Kp+1 family of perfect 1-factorization from the K2p family. Namely, techniques from coding theory are used to prove a new result in graph theory—that the two factorization families are related. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 55
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 38809702
- Full Text :
- https://doi.org/10.1109/TIT.2008.2009850