Abstract Estimering av antalet trianglar i grafströmmar med hjälp av en begränsad mängd minne har blivit ett populärt ämne under det senaste årtiondet. Olika variationer av problemet har studerats, beroende på om grafkanterna tillhandahålls i godtycklig ordning eller som incidenslistor. Med några få undantag har algoritmerna dock övervägt input-only-strömmar. Vi presenterar en ny algoritm som uppskattar antalet trianglar i dynamiska grafströmmar där kanter både kan infogas och tas bort. Vi visar att vår algoritm uppnår bättre tid och utrymme komplexitet än tidigare lösningar för olika grafklasser, till exempel glesa grafer med ett relativt litet antal trianglar. För grafer med konstant transitivitetskoefficient, en vanlig situation i verkliga grafer, är detta den första algoritmen som uppnår konstant bearbetningstid per kant. Resultatet uppnås genom en ny metod som kombinerar provtagning av vertex-tripplar och sparifiering av inmatningskurvan. Under analysen av algoritmen presenterar vi en lägre gräns på antalet parvis oberoende 2-patter i allmänna grafer som kan vara av oberoende intresse. I slutet av pappret diskuterar vi lägre gränser för komplexiteten i triangelräkningsalgoritmer som inte gör några antaganden om grafens struktur.
Det finns också arbete uppskatta antalet trianglar i graf strömmar med både kantinsatser och tar bort REF.
Triangle Counting in Dynamic Graph Streams
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}