Publicación: Propiedades de grafos, hipergrafos y su complejidad algorítmica.
Portada
PDF 
FLIP 
Citas bibliográficas
Gestores Bibliográficos
Indexadores
Código QR
Autores
Director
Autor corporativo
Recolector de datos
Otros/Desconocido
Director audiovisual
Editor/Compilador
Editores
Tipo de Material
Fecha
Cita bibliográfica
Título de serie/ reporte/ volumen/ colección
Es Parte de
Resumen en español
En 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.
Resumen en inglés
In 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.