Publicación:
Propiedades de grafos, hipergrafos y su complejidad algorítmica.

Vista sencilla de ítem
dc.audience
dc.contributor.advisorBorja soto, Jerson Manuelspa
dc.contributor.authorNegrete Madera, Laura Vanesa
dc.date.accessioned2022-09-02T20:47:15Z
dc.date.available2023-09-02
dc.date.available2022-09-02T20:47:15Z
dc.date.issued2022-09-02
dc.description.abstractEn este trabajo estudiamos la complejidad de propiedades de grafos no evasivas, así como la evasividad de algunas propiedades de hipergrafos. Además, en el caso de las propiedades no evasivas damos estrategias que permiten obtener una cota para la complejidad de las mismas. En cuanto a propiedades de hipergrafos, mostramos una generalización del teorema de Yao sobre propiedades de grafos bipartitos, a propiedades de hipergrafos k−partitos k−uniformes.spa
dc.description.abstractIn this work we show the complexity of some known non-evasive graph properties, as well as the evasiveness of some hypergraph properties. Furthermore, in the case of non-evasive properties, we show the strategies that allow us to obtain an upper bound for their complexity. For hypergraph properties, we prove a generalization to k−partite hipergraph properties, of Yao’s theorem on bipartite graph properties.eng
dc.description.degreelevelMaestríaspa
dc.description.degreenameMagíster en Matemáticasspa
dc.description.modalityTrabajos de Investigación y/o Extensiónspa
dc.description.tableofcontentsResumen................................................. IIIspa
dc.description.tableofcontentsAgradecimientos.......................................Vspa
dc.description.tableofcontents1. Preliminares......................................... 3spa
dc.description.tableofcontents1.1. Propiedades de grafos y la conjetura de evasividad . . . . . . . . . . . 3spa
dc.description.tableofcontents1.2. Complejos simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5spa
dc.description.tableofcontents1.3. Enfoque topológico a la evasividad . . . . . . . . . . . . . . . . . . . . . 7spa
dc.description.tableofcontents2. Propiedades no evasivas......................................... 9spa
dc.description.tableofcontents2.1. Propiedad de Carter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9spa
dc.description.tableofcontents2.2. Propiedad de Kleitman . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10spa
dc.description.tableofcontents2.3. Grafos Escorpión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11spa
dc.description.tableofcontents2.4. Propiedad no evasiva más pequeña . . . . . . . . . . . . . . . . . . . . . 14spa
dc.description.tableofcontents2.5. Generalizaciones de la propiedad de Kleitman . . . . . . . . . . . . . . 18spa
dc.description.tableofcontents2.5.1. Primera generalización de la propiedad de Kleitman . . . . . . 19spa
dc.description.tableofcontents2.5.2. Segunda generalización de la propiedad de Kleitman . . . . . . 21spa
dc.description.tableofcontents2.5.3. Tercera generalización de la propiedad de Kleitman . . . . . . . 24spa
dc.description.tableofcontents3. Propiedades de hipergrafos.................................. 27spa
dc.description.tableofcontents3.1. Hipergrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27spa
dc.description.tableofcontents3.2. Extensión a hipergrafos de la propiedad de ser bipartito . . . . . . . . . 29spa
dc.description.tableofcontents4. Conclusiones............................................. 34spa
dc.description.tableofcontentsBibliografía..................................................... 35spa
dc.format.mimetypeapplication/pdfspa
dc.identifier.urihttps://repositorio.unicordoba.edu.co/handle/ucordoba/6529
dc.language.isospaspa
dc.publisherUniversidad de Córdoba
dc.publisher.facultyFacultad de Ciencias Básicasspa
dc.publisher.placeMontería, Córdoba, Colombiaspa
dc.publisher.programMaestría en Matemáticasspa
dc.rightsCopyright Universidad de Córdoba, 2022spa
dc.rights.accessrightsinfo:eu-repo/semantics/embargoedAccessspa
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)spa
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/spa
dc.subject.keywordsComplexityspa
dc.subject.keywordsEvasivenessspa
dc.subject.keywordsGraph propertiesspa
dc.subject.keywordsHypergraph properties.spa
dc.subject.proposalComplejidadspa
dc.subject.proposalEvasividadspa
dc.subject.proposalPropiedades de grafosspa
dc.subject.proposalPropiedades de hipergrafosspa
dc.titlePropiedades de grafos, hipergrafos y su complejidad algorítmica.spa
dc.typeTrabajo de grado - Maestríaspa
dc.type.coarhttp://purl.org/coar/resource_type/c_bdccspa
dc.type.contentTextspa
dc.type.driverinfo:eu-repo/semantics/masterThesisspa
dc.type.redcolhttps://purl.org/redcol/resource_type/TMspa
dc.type.versioninfo:eu-repo/semantics/submittedVersionspa
dcterms.referencesAdamaszek, M. “The smallest nonevasive graph property”. En: Discussiones Mathematicae Graph Theory 34 (mar. de 2013). DOI: 10.7151/dmgt.1766.spa
dcterms.referencesAngel, A. y Borja, J. “Simplicial complexes and the evasivesness conjecture”. En: Graduate J. Math 1 (2016).spa
dcterms.referencesAngel, A. y Borja J. “The Evasiveness Conjecture and Graphs on 2p Vertices”. En: Journal of Graph Theory 91 (mayo de 2019). DOI: 10.1002/jgt. 22419.spa
dcterms.referencesChronaki, C. “A survey of Evasiveness: Lower Bounds on the DecisionTree Complexity of Boolean Functions”. En: (ene. de 2000).spa
dcterms.referencesEngström, A. “Transitive graphs in counterexamples to Karp’s conjecture”. En: (ene. de 2006).spa
dcterms.referencesJonsson, J. Simplicial Complexes of Graphs. Vol. 1928. Ene. de 2008. ISBN: 978-3-540-75858-7. DOI: 10.1007/978-3-540-75859-4.spa
dcterms.referencesKahn, J., Saks, M., y Sturtevant, D. “A topological approach to evasiveness”. En: vol. 4. Dic. de 1983, págs. 31-33. ISBN: 0-8186-0508-1. DOI: 10. 1109/SFCS.1983.4.spa
dcterms.referencesLenstra, H.W., Best, M.R., y van Emde Boas, P. “A sharpened version of the Aanderaa-Rosenberg conjecture”. En: Report 30/74, Mathematisch Centrum Amsterdam (1974) (ene. de 1974).spa
dcterms.referencesLongueville, M. A Course in Topological Combinatorics. Ene. de 2013. ISBN: 978-1-4419-7909-4. DOI: 10.1007/978-1-4419-7910-0.spa
dcterms.referencesMiller, C. “Evasiveness of Graph Properties and Topological Fixed-Point Theorems”. En: Foundations and Trends in Theoretical Computer Science 7 (jun. de 2013). DOI: 10.1561/0400000055.spa
dcterms.referencesRivest, R. y Vuillemin, J. “A Generalization and Proof of the AanderaaRosenberg Conjecture”. En: ene. de 1975, págs. 6-11. DOI: 10.1145/800116. 803747.spa
dspace.entity.typePublication
oaire.accessrightshttp://purl.org/coar/access_right/c_f1cfspa
oaire.versionhttp://purl.org/coar/version/c_ab4af688f83e57aaspa
Archivos
Bloque original
Mostrando 1 - 2 de 2
Miniatura
Nombre:
negretemaderalauravanesa.pdf
Tamaño:
383.91 KB
Formato:
Adobe Portable Document Format
Descripción:
Descargar
No hay miniatura disponible
Nombre:
AutorizaciónPublicación..pdf
Tamaño:
282.9 KB
Formato:
Adobe Portable Document Format
Descripción:
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
14.48 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
B.J.A. Tesis