I detta papper studerar vi grafproblem i den dynamiska streaming modellen, där indata definieras av en sekvens av kantinsättningar och raderingar. Eftersom många naturliga problem kräver utrymme, där n är antalet hörn, är befintliga verk främst inriktade på att utforma O(n · poly log n) rymdalgoritmer. Även sublinear i antalet kanter för täta grafer, kan det fortfarande vara för stor för många tillämpningar (t.ex., n är enorm eller grafen är gles). I detta arbete ger vi en-pass algoritmer som slår denna rymdbarriär för två klasser av problem. Vi presenterar o(n) utrymme algoritmer för att uppskatta antalet anslutna komponenter med additivt fel εn i en allmän graf och (1 + ε)-ungefärande vikten av minsta spännvidd träd i en ansluten graf med avgränsade kant vikter, för alla små konstant ε > 0. Den senare förbättrar den tidigare O(n · poly log n) rymdalgoritm som ges av Ahn et al. (SODA 2012) för samma kategori av grafer. Vi initierar studien av ungefärliga graf egendom testning i den dynamiska streaming modellen, där vi vill skilja grafer som uppfyller egenskapen från grafer som är ε-långt från att ha fastigheten. Vi anser att problemet med att testa k-kant konnektivitet, k-vertex konnektivitet, cykelfrihet och bipartiteness (av plana grafer), där vi tillhandahåller algoritmer som använder ungefär O(n 1−ε · poly log n) utrymme, som är o(n) för alla konstant ε. För att komplettera våra algoritmer presenterar vi utrymme lägre gränser för dessa problem, vilket visar att ett sådant beroende av ε är nödvändigt.
Det har också funnits arbete med fastighetstestning i den strömmande modellen REF.
Dynamic Graph Stream Algorithms in o(n) Space
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}