Butenko, Sergiy; Pardalos, Panos; Sergienko, Ivan; Shylo, Vladimir; Stetsyuk, Petro Estimating the size of correcting codes using extremal graph problems. (English) Zbl 1181.94137 Pearce, Charles (ed.) et al., Optimization. Structure and applications. New York, NY: Springer (ISBN 978-0-387-98095-9/hbk; 978-0-387-98096-6/ebook). Springer Optimization and Its Applications 32, 227-243 (2009). Summary: Some of the fundamental problems in coding theory can be formulated as extremal graph problems. Finding estimates of the size of correcting codes is important from both theoretical and practical perspectives. We solve the problem of finding the largest correcting codes using previously developed algorithms for optimization problems in graphs. We report new exact solutions and estimates.For the entire collection see [Zbl 1357.49008]. Cited in 5 Documents MSC: 94B50 Synchronization error-correcting codes 90C27 Combinatorial optimization Keywords:maximum independent set; graph coloring; error-correcting codes; coding theory; combinatorial optimization Software:DIMACS PDFBibTeX XMLCite \textit{S. Butenko} et al., Springer Optim. Appl. 32, 227--243 (2009; Zbl 1181.94137) Full Text: DOI