2013 

1.  RuizVanoye, Jorge A; PérezOrtega, Joaquín; R., Rodolfo Pazos A; DíazParra, Ocotlán; FraireHuacuja, Hector J; FraustoSolis, Juan; ReyesSalgado, Gerardo; CruzReyes, Laura Application of formal languages in the polynomial transformations of instances between NPcomplete problems Journal Article In: Journal of Zhejiang UniversitySCIENCE C (Computers & Electronics), 14 (8), pp. 623633, 2013, ISSN: 1869196X. Abstract  Links  BibTeX  Tags: Papers in the Science Citation Index Expanded, polynomial transformations @article{JCR5, title = {Application of formal languages in the polynomial transformations of instances between NPcomplete problems}, author = {Jorge A. RuizVanoye and Joaquín PérezOrtega and Rodolfo A. Pazos R. and Ocotlán DíazParra and Hector J. FraireHuacuja and Juan FraustoSolis and Gerardo ReyesSalgado and Laura CruzReyes}, url = {http://link.springer.com/article/10.1631/jzus.C1200349}, doi = {10.1631/jzus.C1200349}, issn = {1869196X}, year = {2013}, date = {20130207}, journal = {Journal of Zhejiang UniversitySCIENCE C (Computers & Electronics)}, volume = {14}, number = {8}, pages = {623633}, abstract = {We propose the usage of formal languages for expressing instances of NPcomplete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NPcomplete problems, which differs from Garey and Johnson’s. Unlike most transformations which are used for proving that a problem is NPcomplete based on the NPcompleteness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.}, keywords = {Papers in the Science Citation Index Expanded, polynomial transformations}, pubstate = {published}, tppubtype = {article} } We propose the usage of formal languages for expressing instances of NPcomplete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NPcomplete problems, which differs from Garey and Johnson’s. Unlike most transformations which are used for proving that a problem is NPcomplete based on the NPcompleteness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B. 
2011 

2.  RuizVanoye, Jorge A; PérezOrtega, Joaquín; R., Rodolfo Pazos A; DíazParra, Ocotlán; FraustoSolís, Juan; FraireHuacuja, Hector J; CruzReyes, Laura; MartínezFlores, José A Survey of Polynomial Transformations between NPComplete problems Journal Article In: Journal of Computational and Applied Mathematics, 235 (16), pp. 48514865, 2011, ISSN: 03770427. Abstract  Links  BibTeX  Tags: Papers in the Science Citation Index Expanded, polynomial transformations @article{JCR7, title = {Survey of Polynomial Transformations between NPComplete problems}, author = {Jorge A. RuizVanoye and Joaquín PérezOrtega and Rodolfo A. Pazos R. and Ocotlán DíazParra and Juan FraustoSolís and Hector J. FraireHuacuja and Laura CruzReyes and José A. MartínezFlores}, url = {http://dx.doi.org/doi:10.1016/j.cam.2011.02.018}, doi = {10.1016/j.cam.2011.02.018}, issn = {03770427}, year = {2011}, date = {20110207}, journal = {Journal of Computational and Applied Mathematics}, volume = {235}, number = {16}, pages = {48514865}, abstract = {This paper aims at being a guide to understand polynomial transformations and polynomial reductions between NPcomplete 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 NPcomplete problems. Finally, this paper includes a digraph with the historical reductions/transformations between instances of NPcomplete problems and introduces the term family of polynomial transformations.}, keywords = {Papers in the Science Citation Index Expanded, polynomial transformations}, pubstate = {published}, tppubtype = {article} } This paper aims at being a guide to understand polynomial transformations and polynomial reductions between NPcomplete 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 NPcomplete problems. Finally, this paper includes a digraph with the historical reductions/transformations between instances of NPcomplete problems and introduces the term family of polynomial transformations. 
Publications
2013 

1.  Application of formal languages in the polynomial transformations of instances between NPcomplete problems Journal Article In: Journal of Zhejiang UniversitySCIENCE C (Computers & Electronics), 14 (8), pp. 623633, 2013, ISSN: 1869196X. 
2011 

2.  Survey of Polynomial Transformations between NPComplete problems Journal Article In: Journal of Computational and Applied Mathematics, 235 (16), pp. 48514865, 2011, ISSN: 03770427. 