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

• Espuny Díaz, Alberto ^[1]
  1. [1] University of Birmingham

     University of Birmingham

     Reino Unido

     
• Localización: TEMat: Divulgación de trabajos de estudiantes de matemáticas, ISSN-e 2530-9633, Nº. 3, 2019, págs. 87-100
• Idioma: español
• Enlaces
  • Texto completo
• Resumen
  • español

    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.

  • English

    Property testing refers to a group of algorithmic techniques developed to achieve decision algorithms that work in sublinear time at the expense of some accuracy in the algorithms’ output. In this paper, we present a brief discussion about property testing, explaining its usefulness and how to evaluate the efficiency of property testing algorithms. In particular, we consider algorithms that test graph properties. We present the three most common property testing models for graphs and, as an example, show how to test one property, triangle-freeness, in each of these models