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

En 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 da...

Full description

Autores:
Montoya, J. Andrés
Tipo de recurso:
Trabajo de grado de pregrado
Fecha de publicación:
2009
Institución:
Universidad Autónoma de Bucaramanga - UNAB
Repositorio:
Repositorio UNAB
Idioma:
spa
OAI Identifier:
oai:repository.unab.edu.co:20.500.12749/8974
Acceso en línea:
http://hdl.handle.net/20.500.12749/8974
Palabra clave:
Máquinas de Turing
Clases de complejidad
Complejidad paramétrica
Algoritmos eficientes
Turing machines
Complexity classes
Parametric complexity
Efficient algorithms
Research
Graph mining
Analysis
patterns
Complexity
Turing machines
Efficient algorithms
Investigación
Minería de grafos
Análisis
Patrones
Complejidad
Máquinas de turing
Algoritmos eficientes
Rights
License
Derechos de autor 2009 Revista Colombiana de Computación
id UNAB2_a33a1c21c699bf44c232b66b01a770ef
oai_identifier_str oai:repository.unab.edu.co:20.500.12749/8974
network_acronym_str UNAB2
network_name_str Repositorio UNAB
repository_id_str
dc.title.none.fl_str_mv La complejidad paramétrica de minar grafos 2, resultados positivos
dc.title.translated.eng.fl_str_mv The parametric complexity of mining graphs 2, positive results
title La complejidad paramétrica de minar grafos 2, resultados positivos
spellingShingle La complejidad paramétrica de minar grafos 2, resultados positivos
Máquinas de Turing
Clases de complejidad
Complejidad paramétrica
Algoritmos eficientes
Turing machines
Complexity classes
Parametric complexity
Efficient algorithms
Research
Graph mining
Analysis
patterns
Complexity
Turing machines
Efficient algorithms
Investigación
Minería de grafos
Análisis
Patrones
Complejidad
Máquinas de turing
Algoritmos eficientes
title_short La complejidad paramétrica de minar grafos 2, resultados positivos
title_full La complejidad paramétrica de minar grafos 2, resultados positivos
title_fullStr La complejidad paramétrica de minar grafos 2, resultados positivos
title_full_unstemmed La complejidad paramétrica de minar grafos 2, resultados positivos
title_sort La complejidad paramétrica de minar grafos 2, resultados positivos
dc.creator.fl_str_mv Montoya, J. Andrés
dc.contributor.author.spa.fl_str_mv Montoya, J. Andrés
dc.subject.none.fl_str_mv Máquinas de Turing
Clases de complejidad
Complejidad paramétrica
Algoritmos eficientes
topic Máquinas de Turing
Clases de complejidad
Complejidad paramétrica
Algoritmos eficientes
Turing machines
Complexity classes
Parametric complexity
Efficient algorithms
Research
Graph mining
Analysis
patterns
Complexity
Turing machines
Efficient algorithms
Investigación
Minería de grafos
Análisis
Patrones
Complejidad
Máquinas de turing
Algoritmos eficientes
dc.subject.keywords.eng.fl_str_mv Turing machines
Complexity classes
Parametric complexity
Efficient algorithms
Research
Graph mining
Analysis
patterns
Complexity
Turing machines
Efficient algorithms
dc.subject.lemb.spa.fl_str_mv Investigación
Minería de grafos
Análisis
Patrones
dc.subject.proposal.spa.fl_str_mv Complejidad
Máquinas de turing
Algoritmos eficientes
description En 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.
publishDate 2009
dc.date.issued.none.fl_str_mv 2009-06-01
dc.date.accessioned.none.fl_str_mv 2020-10-27T00:20:49Z
dc.date.available.none.fl_str_mv 2020-10-27T00:20:49Z
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/article
dc.type.local.spa.fl_str_mv Artículo
dc.type.coar.none.fl_str_mv http://purl.org/coar/resource_type/c_7a1f
dc.type.redcol.none.fl_str_mv http://purl.org/redcol/resource_type/CJournalArticle
format http://purl.org/coar/resource_type/c_7a1f
dc.identifier.issn.none.fl_str_mv 2539-2115
1657-2831
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/20.500.12749/8974
dc.identifier.instname.spa.fl_str_mv instname:Universidad Autónoma de Bucaramanga UNAB
dc.identifier.repourl.none.fl_str_mv repourl:https://repository.unab.edu.co
identifier_str_mv 2539-2115
1657-2831
instname:Universidad Autónoma de Bucaramanga UNAB
repourl:https://repository.unab.edu.co
url http://hdl.handle.net/20.500.12749/8974
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1138/1162
dc.relation.uri.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1138
dc.relation.references.none.fl_str_mv ] N. Alon, J. Spencer. The Probabilistic Method. Wiley, 2a. edicion, 2000
1] 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
3] V. Dalmau and P. Jonsson. The complexity of counting homomorphism seen from the other side. Theoretical Computer Science, 329:315-323, 2004
] R. Diestel. Graph Theory. Springer Verlag 200
5] R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 1999
6] J. Flum and M. Grohe. The parameterized complexity of counting problems. SIAM Journal of Computing, 33(4):892-922, 2004
] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006
9] M. Grohe. The complexity of homomorphism and constraint satisfaction problem seen from the other side, Journal of the ACM, 54(1), ó ,2007
0] J. A. Montoya. La complejidad paramÈtrica de minar grafos I, resultados negativos. Sometido, Revista Colombiana de Computación
] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Boston MA, 1996.
] C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
] S. Toda. P P is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991.
dc.rights.none.fl_str_mv Derechos de autor 2009 Revista Colombiana de Computación
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rights.uri.none.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/2.5/co/
dc.rights.creativecommons.*.fl_str_mv Atribución-NoComercial-SinDerivadas 2.5 Colombia
rights_invalid_str_mv Derechos de autor 2009 Revista Colombiana de Computación
http://creativecommons.org/licenses/by-nc-sa/4.0/
http://creativecommons.org/licenses/by-nc-nd/2.5/co/
Atribución-NoComercial-SinDerivadas 2.5 Colombia
http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
dc.source.none.fl_str_mv Revista Colombiana de Computación; Vol. 10 Núm. 1 (2009): Revista Colombiana de Computación; 1-20
institution Universidad Autónoma de Bucaramanga - UNAB
bitstream.url.fl_str_mv https://repository.unab.edu.co/bitstream/20.500.12749/8974/1/2009_Montoya_J_Andres.pdf
https://repository.unab.edu.co/bitstream/20.500.12749/8974/2/2009_Montoya_J_Andres.pdf.jpg
bitstream.checksum.fl_str_mv 10ec6702c92caadebcc4d5efafae95df
d10a73331ba2e36b2c3935ca0098c85d
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional | Universidad Autónoma de Bucaramanga - UNAB
repository.mail.fl_str_mv repositorio@unab.edu.co
_version_ 1814277249208156160
spelling Montoya, J. Andrés9a16b00e-fbdf-4af6-ac0c-1ab42d1b6a572020-10-27T00:20:49Z2020-10-27T00:20:49Z2009-06-012539-21151657-2831http://hdl.handle.net/20.500.12749/8974instname:Universidad Autónoma de Bucaramanga UNABrepourl:https://repository.unab.edu.coEn 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.In 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.application/pdfspaUniversidad Autónoma de Bucaramanga UNABhttps://revistas.unab.edu.co/index.php/rcc/article/view/1138/1162https://revistas.unab.edu.co/index.php/rcc/article/view/1138] N. Alon, J. Spencer. The Probabilistic Method. Wiley, 2a. edicion, 20001] 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, 20023] V. Dalmau and P. Jonsson. The complexity of counting homomorphism seen from the other side. Theoretical Computer Science, 329:315-323, 2004] R. Diestel. Graph Theory. Springer Verlag 2005] R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 19996] J. Flum and M. Grohe. The parameterized complexity of counting problems. SIAM Journal of Computing, 33(4):892-922, 2004] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 20069] M. Grohe. The complexity of homomorphism and constraint satisfaction problem seen from the other side, Journal of the ACM, 54(1), ó ,20070] J. A. Montoya. La complejidad paramÈtrica de minar grafos I, resultados negativos. Sometido, Revista Colombiana de Computación] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Boston MA, 1996.] C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.] S. Toda. P P is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991.Derechos de autor 2009 Revista Colombiana de Computaciónhttp://creativecommons.org/licenses/by-nc-sa/4.0/http://creativecommons.org/licenses/by-nc-nd/2.5/co/Atribución-NoComercial-SinDerivadas 2.5 Colombiahttp://purl.org/coar/access_right/c_abf2Revista Colombiana de Computación; Vol. 10 Núm. 1 (2009): Revista Colombiana de Computación; 1-20Máquinas de TuringClases de complejidadComplejidad paramétricaAlgoritmos eficientesTuring machinesComplexity classesParametric complexityEfficient algorithmsResearchGraph miningAnalysispatternsComplexityTuring machinesEfficient algorithmsInvestigaciónMinería de grafosAnálisisPatronesComplejidadMáquinas de turingAlgoritmos eficientesLa complejidad paramétrica de minar grafos 2, resultados positivosThe parametric complexity of mining graphs 2, positive resultsinfo:eu-repo/semantics/articleArtículohttp://purl.org/coar/resource_type/c_7a1fhttp://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/redcol/resource_type/CJournalArticleORIGINAL2009_Montoya_J_Andres.pdf2009_Montoya_J_Andres.pdfArtículoapplication/pdf210238https://repository.unab.edu.co/bitstream/20.500.12749/8974/1/2009_Montoya_J_Andres.pdf10ec6702c92caadebcc4d5efafae95dfMD51open accessTHUMBNAIL2009_Montoya_J_Andres.pdf.jpg2009_Montoya_J_Andres.pdf.jpgIM Thumbnailimage/jpeg7156https://repository.unab.edu.co/bitstream/20.500.12749/8974/2/2009_Montoya_J_Andres.pdf.jpgd10a73331ba2e36b2c3935ca0098c85dMD52open access20.500.12749/8974oai:repository.unab.edu.co:20.500.12749/89742022-11-24 12:44:42.94open accessRepositorio Institucional | Universidad Autónoma de Bucaramanga - UNABrepositorio@unab.edu.co