Finding maximum independent sets in graphs arising from coding theory Conference Paper uri icon


  • New results are presented concerning binary correcting codes, such as deletion-correcting codes, transposition-correction codes, and codes for the Z-channel. These codes are important due to the possibility of packet loss and corruption on internet transmissions. It is known that the problem of finding the largest correcting codes can be reduced to a well-known combinatorial optimization problem on graphs, the maximum independent set problem. A general scheme of organizing a local search for the maximum independent set problem is discussed. Based on the developed heuristics, an exact branch-and-bound algorithm is proposed, which is able to find exact solutions for graphs with over 500 vertices within a reasonable time.

published proceedings

  • Proceedings of the ACM Symposium on Applied Computing

author list (cited authors)

  • Butenko, S., Pardalos, P., Sergienko, I., & Shylo, V.

complete list of authors

  • Butenko, S||Pardalos, P||Sergienko, I||Shylo, V

publication date

  • January 2002