La complejidad paramétrica de minar grafos 2, resultados positivos

Vista sencilla de ítem
dc.contributor.authorMontoya, J. Andrésspa
dc.date.accessioned2020-10-27T00:20:49Z
dc.date.available2020-10-27T00:20:49Z
dc.date.issued2009-06-01
dc.description.abstractEn este artículo analizamos la complejidad paramétrica de algunos problemas típicos en minería de grafos, específicamente nosotros analizamos la complejidad paramétrica del problema de listado consistente en: Dado G un grafo-input, liste todos los subgrafos frecuentes de G de un tamaño dado. En el artículo se prueban cotas superiores para algunas restricciones adecuadas del problema.spa
dc.description.abstractenglishIn this paper we analyze the parameterized complexity of graphmining tasks, speciÖcally we analyze the parameterized complexity of the list-ing problem consistent in: Given an input graphG;list the frequent subgraphsofGof a given size. In this paper we prove some upper bounds for suitablerestrictions of this problem.eng
dc.format.mimetypeapplication/pdfspa
dc.identifier.instnameinstname:Universidad Autónoma de Bucaramanga UNABspa
dc.identifier.issn2539-2115
dc.identifier.issn1657-2831
dc.identifier.repourlrepourl:https://repository.unab.edu.co
dc.identifier.urihttp://hdl.handle.net/20.500.12749/8974
dc.language.isospaspa
dc.publisherUniversidad Autónoma de Bucaramanga UNAB
dc.relationhttps://revistas.unab.edu.co/index.php/rcc/article/view/1138/1162
dc.relation.references] N. Alon, J. Spencer. The Probabilistic Method. Wiley, 2a. edicion, 2000
dc.relation.references1] V. Arvind and V. Raman. Approximation algorithms for some parameterized counting problems. In P. Bose and P. Morin, editors, Proceedings of the 13th Annual International Symposium on Algorithms and Computation, Volume 2518 of Lecture Notes in Computer Science, pages 453-464. Springer-Verlag, 2002
dc.relation.references3] V. Dalmau and P. Jonsson. The complexity of counting homomorphism seen from the other side. Theoretical Computer Science, 329:315-323, 2004
dc.relation.references] R. Diestel. Graph Theory. Springer Verlag 200
dc.relation.references5] R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 1999
dc.relation.references6] J. Flum and M. Grohe. The parameterized complexity of counting problems. SIAM Journal of Computing, 33(4):892-922, 2004
dc.relation.references] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006
dc.relation.references9] M. Grohe. The complexity of homomorphism and constraint satisfaction problem seen from the other side, Journal of the ACM, 54(1), ó ,2007
dc.relation.references0] J. A. Montoya. La complejidad paramÈtrica de minar grafos I, resultados negativos. Sometido, Revista Colombiana de Computación
dc.relation.references] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Boston MA, 1996.
dc.relation.references] C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
dc.relation.references] S. Toda. P P is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991.
dc.relation.urihttps://revistas.unab.edu.co/index.php/rcc/article/view/1138
dc.rightsDerechos de autor 2009 Revista Colombiana de Computación
dc.rights.accessrightsinfo:eu-repo/semantics/openAccessspa
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 2.5 Colombia*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/4.0/*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.5/co/
dc.sourceRevista Colombiana de Computación; Vol. 10 Núm. 1 (2009): Revista Colombiana de Computación; 1-20
dc.subjectMáquinas de Turing
dc.subjectClases de complejidad
dc.subjectComplejidad paramétrica
dc.subjectAlgoritmos eficientes
dc.subject.keywordsTuring machineseng
dc.subject.keywordsComplexity classeseng
dc.subject.keywordsParametric complexityeng
dc.subject.keywordsEfficient algorithmseng
dc.subject.keywordsResearcheng
dc.subject.keywordsGraph miningeng
dc.subject.keywordsAnalysiseng
dc.subject.keywordspatternseng
dc.subject.keywordsComplexityeng
dc.subject.keywordsTuring machineseng
dc.subject.keywordsEfficient algorithmseng
dc.subject.lembInvestigaciónspa
dc.subject.lembMinería de grafosspa
dc.subject.lembAnálisisspa
dc.subject.lembPatronesspa
dc.subject.proposalComplejidadspa
dc.subject.proposalMáquinas de turingspa
dc.subject.proposalAlgoritmos eficientesspa
dc.titleLa complejidad paramétrica de minar grafos 2, resultados positivos
dc.title.translatedThe parametric complexity of mining graphs 2, positive resultseng
dc.type.coarhttp://purl.org/coar/resource_type/c_7a1f
dc.type.driverinfo:eu-repo/semantics/article
dc.type.hasversioninfo:eu-repo/semantics/acceptedVersion
dc.type.localArtículospa
dc.type.redcolhttp://purl.org/redcol/resource_type/CJournalArticle

Archivos

Bloque original

Mostrando 1 - 1 de 1
Miniatura
Nombre:
2009_Montoya_J_Andres.pdf
Tamaño:
205.31 KB
Formato:
Adobe Portable Document Format
Descripción:
Artículo
Descargar

Colecciones

Revista Colombiana de Computación