La complejidad paramétrica de minar grafos 1, resultados negativos

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 de G de un tamaño dado. En el a...

Full description

Autores:
Montoya, Juan 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/8973
Acceso en línea:
http://hdl.handle.net/20.500.12749/8973
Palabra clave:
Máquinas de Turing
Clases de complejidad
Complejidad paramétrica
Algoritmos eficientes
Turing machines
Complexity classes
Parametric complexity
Efficient algorithms
Graph mining
Computational task
Parameterization
Problems
Máquinas de turing
Complejidad paramétrica
Algoritmos eficientes
Investigación
Minería de grafos
Tarea computacional
Parametrización
Problemas
Rights
License
Derechos de autor 2009 Revista Colombiana de Computación
id UNAB2_79c4e3aa3d25c59021d89f6ac71a0073
oai_identifier_str oai:repository.unab.edu.co:20.500.12749/8973
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 1, resultados negativos
dc.title.translated.eng.fl_str_mv The parametric complexity of mining graphs 1, negative results
title La complejidad paramétrica de minar grafos 1, resultados negativos
spellingShingle La complejidad paramétrica de minar grafos 1, resultados negativos
Máquinas de Turing
Clases de complejidad
Complejidad paramétrica
Algoritmos eficientes
Turing machines
Complexity classes
Parametric complexity
Efficient algorithms
Graph mining
Computational task
Parameterization
Problems
Máquinas de turing
Complejidad paramétrica
Algoritmos eficientes
Investigación
Minería de grafos
Tarea computacional
Parametrización
Problemas
title_short La complejidad paramétrica de minar grafos 1, resultados negativos
title_full La complejidad paramétrica de minar grafos 1, resultados negativos
title_fullStr La complejidad paramétrica de minar grafos 1, resultados negativos
title_full_unstemmed La complejidad paramétrica de minar grafos 1, resultados negativos
title_sort La complejidad paramétrica de minar grafos 1, resultados negativos
dc.creator.fl_str_mv Montoya, Juan Andrés
dc.contributor.author.spa.fl_str_mv Montoya, Juan Andrés
dc.contributor.googlescholar.spa.fl_str_mv Montoya, Juan Andrés [NWPoQFcAAAAJ]
dc.contributor.orcid.spa.fl_str_mv Montoya, Juan Andrés [0000-0002-9897-3710]
dc.contributor.researchgate.spa.fl_str_mv Montoya, Juan Andrés [Juan-Montoya-23]
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
Graph mining
Computational task
Parameterization
Problems
Máquinas de turing
Complejidad paramétrica
Algoritmos eficientes
Investigación
Minería de grafos
Tarea computacional
Parametrización
Problemas
dc.subject.keywords.eng.fl_str_mv Turing machines
Complexity classes
Parametric complexity
Efficient algorithms
Graph mining
Computational task
Parameterization
Problems
dc.subject.lemb.spa.fl_str_mv Máquinas de turing
Complejidad paramétrica
Algoritmos eficientes
Investigación
dc.subject.proposal.spa.fl_str_mv Minería de grafos
Tarea computacional
Parametrización
Problemas
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 de G de un tamaño dado. En el artículo se prueban algunas cotas inferiores para este 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/8973
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/8973
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/1137/1161
dc.relation.uri.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1137
dc.relation.references.none.fl_str_mv rencias [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-V
2002. [2] V. Dalmau and P. Jonsson. The complexity of counting homomorphism seen from the other side. Theoretical Computer Science, 329:31
[3] R. Diestel. Graph theory. Springer
[4] R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-V
[5] J. Flum and M. Grohe. The parameterized complexity of counting problems. SIAM Journal of Computing, 33(4):89
[6] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-V
[7] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Bosto
[8] M. Grohe. The complexity of homomorphism and constraint satisfaction problem seen from the other side, Journal of the ACM, 54(
[9] J. Kobler; U Schoning and J Toran. The Graph isomorphism problem, its structural complexity. Springer V
[10] C.H. Papadimitriou. Computational Complexity. Addison-
[11] S. Toda. P P is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865
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-17
institution Universidad Autónoma de Bucaramanga - UNAB
bitstream.url.fl_str_mv https://repository.unab.edu.co/bitstream/20.500.12749/8973/1/2009_La%20complejidad%20param%c3%a9trica%20de%20minar%20grafos%201_resultados%20negativos.pdf
https://repository.unab.edu.co/bitstream/20.500.12749/8973/2/2009_La%20complejidad%20param%c3%a9trica%20de%20minar%20grafos%201_resultados%20negativos.pdf.jpg
bitstream.checksum.fl_str_mv 6673d7520652804cff8583d325d8b309
900f7594f15d8892e3822869ddefd102
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_ 1814277323613011968
spelling Montoya, Juan Andrésbc269a27-36b5-46b5-8c5a-00f331922017Montoya, Juan Andrés [NWPoQFcAAAAJ]Montoya, Juan Andrés [0000-0002-9897-3710]Montoya, Juan Andrés [Juan-Montoya-23]2020-10-27T00:20:49Z2020-10-27T00:20:49Z2009-06-012539-21151657-2831http://hdl.handle.net/20.500.12749/8973instname: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 de G de un tamaño dado. En el artículo se prueban algunas cotas inferiores para este problema.In this article we analyze the parametric complexity of some typical problems in graph mining, specifically we analyze the parametric complexity of the listing problem consisting of: Given G an input-graph, list all subgraphs of G of a given size. The article tests some lower bounds for this problem.application/pdfspaUniversidad Autónoma de Bucaramanga UNABhttps://revistas.unab.edu.co/index.php/rcc/article/view/1137/1161https://revistas.unab.edu.co/index.php/rcc/article/view/1137rencias [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-V2002. [2] V. Dalmau and P. Jonsson. The complexity of counting homomorphism seen from the other side. Theoretical Computer Science, 329:31[3] R. Diestel. Graph theory. Springer[4] R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-V[5] J. Flum and M. Grohe. The parameterized complexity of counting problems. SIAM Journal of Computing, 33(4):89[6] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer-V[7] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Bosto[8] M. Grohe. The complexity of homomorphism and constraint satisfaction problem seen from the other side, Journal of the ACM, 54([9] J. Kobler; U Schoning and J Toran. The Graph isomorphism problem, its structural complexity. Springer V[10] C.H. Papadimitriou. Computational Complexity. Addison-[11] S. Toda. P P is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865Derechos 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-17Máquinas de TuringClases de complejidadComplejidad paramétricaAlgoritmos eficientesTuring machinesComplexity classesParametric complexityEfficient algorithmsGraph miningComputational taskParameterizationProblemsMáquinas de turingComplejidad paramétricaAlgoritmos eficientesInvestigaciónMinería de grafosTarea computacionalParametrizaciónProblemasLa complejidad paramétrica de minar grafos 1, resultados negativosThe parametric complexity of mining graphs 1, negative 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_La complejidad paramétrica de minar grafos 1_resultados negativos.pdf2009_La complejidad paramétrica de minar grafos 1_resultados negativos.pdfArtículoapplication/pdf191196https://repository.unab.edu.co/bitstream/20.500.12749/8973/1/2009_La%20complejidad%20param%c3%a9trica%20de%20minar%20grafos%201_resultados%20negativos.pdf6673d7520652804cff8583d325d8b309MD51open accessTHUMBNAIL2009_La complejidad paramétrica de minar grafos 1_resultados negativos.pdf.jpg2009_La complejidad paramétrica de minar grafos 1_resultados negativos.pdf.jpgIM Thumbnailimage/jpeg7145https://repository.unab.edu.co/bitstream/20.500.12749/8973/2/2009_La%20complejidad%20param%c3%a9trica%20de%20minar%20grafos%201_resultados%20negativos.pdf.jpg900f7594f15d8892e3822869ddefd102MD52open access20.500.12749/8973oai:repository.unab.edu.co:20.500.12749/89732022-11-24 20:02:27.311open accessRepositorio Institucional | Universidad Autónoma de Bucaramanga - UNABrepositorio@unab.edu.co

Publicaciones similares