Artículo: «Buscando triángulos en grafos muy grandes: un ejemplo de property testing»

Por Alberto Espuny Díaz.
En: TEMat, 3 (2019).

Resumen

El property testing hace referencia a un conjunto de técnicas algorítmicas que se han desarrollado para conseguir algoritmos decisionales que trabajen en tiempo sublineal en el tamaño de la entrada a cambio de perder precisión en la respuesta del algoritmo. En este artículo presentamos una breve discusión sobre el property testing, explicando el porqué de su utilidad y cómo valorar su eficiencia. En particular, nos centramos en algoritmos que comprueban propiedades en grafos, presentando los tres modelos más utilizados para comprobar estas propiedades y un ejemplo de cómo tratar una propiedad, la ausencia de triángulos, en cada uno de ellos.


Descarga: «Buscando triángulos en grafos muy grandes: un ejemplo de property testing».

Palabras clave

, , , , , .

Entrada BibTeX

@article{TEMat:2019-p87,
    title = {Buscando triángulos en grafos muy grandes: un ejemplo de property testing},
    author = {Espuny Díaz, Alberto},
    year = {2019},
    journal = {{TEMat}},
    volume = {3},
    issn = {2530-9633},
    pages = {87-100},
    url = {https://temat.es/articulo/2019-p87/},
}