Survey of Polynomial Transformations between NP-Complete problems

  • Ruiz-Vanoye, Jorge A.
  • Pérez-Ortega, Joaquín
  • R., Rodolfo A. Pazos
  • Díaz-Parra, Ocotlán
  • Frausto-Solís, Juan
  • Fraire-Huacuja, Hector J.
  • Cruz-Reyes, Laura
  • Martínez-Flores, José A.
Abstract:
This paper aims at being a guide to understand polynomial transformations and polynomial reductions between NP-complete problems by presenting the methodologies for polynomial reductions/transformations and the differences between reductions and transformations. To this end the article shows examples of polynomial reductions/transformations and the restrictions to reduce/transform between NP-complete problems. Finally, this paper includes a digraph with the historical reductions/transformations between instances of NP-complete problems and introduces the term family of polynomial transformations.
Research areas:
Year:
2011
Type of Publication:
Article
Keywords:
Polynomial transformations; NP-complete; Survey
Journal:
Journal of Computational and Applied Mathematics
Volume:
235
Number:
16
Pages:
4851-4865
ISSN:
0377-0427
DOI:
http://dx.doi.org/10.1016/j.cam.2011.02.018
Hits: 42