Vol. 3 (2019)
Artículos

Buscando triángulos en grafos muy grandes: un ejemplo de property testing

Alberto Espuny Díaz
University of Birmingham
TEMat, 3 (2019) - portada

Publicado 28/05/2019

Palabras clave

  • algoritmos,
  • complejidad,
  • grafos,
  • libre de triángulos,
  • property testing,
  • regularidad
  • ...Más
    Menos

Cómo citar

Espuny Díaz, Alberto. «Buscando triángulos en grafos muy grandes: un ejemplo de property testing». En: TEMat, 3 (2019), págs. 87-100. ISSN: 2530-9633.URL: https://temat.es/articulo/2019-p87.

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.