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...
- 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_ |
1808410535612383232 |
| 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 |