Abstrakt. Problemet med (ungefär) att räkna antalet trianglar i en graf är ett av de grundläggande problemen i grafteorin. I detta dokument studerar vi problemet i den strömmande modellen. Vi studerar den mängd minne som krävs av en randomiserad algoritm för att lösa detta problem. Om algoritmen tillåts passera över strömmen, presenterar vi en bästa möjliga nedre gräns av  och (m) för grafer G med m kanter på n hörn. Om ett konstant antal pass är tillåtet, visar vi en lägre gräns för  ska (m/T ), T antalet trianglar. Vi matchar på något sätt denna nedre gräns med en 2-pass O(m/T 1/3 )-minnesalgoritm som löser problemet med att skilja grafer utan trianglar från grafer med minst T-trianglar. Vi presenterar en ny graf parameter ρ(G) - triangelns densitet, och förmodar att utrymmet komplexitet trianglar problemet är  och (m/ρ(G)). Vi matchar detta med en andra algoritm som löser det särskiljande problemet med hjälp av O(m/ρ(G)-minne.
Bravermanet al. REF gav en två-pass O(m/T 1/3 )-rymd algoritm för att upptäcka om inmatningskurvan är triangelfri eller det har minst T många trianglar.
How Hard is Counting Triangles in the Streaming Model
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}