Analysera massiva datamängder har varit en av de viktigaste motivationerna för att studera strömmande algoritmer. Under de senaste åren har betydande framsteg gjorts när det gäller att analysera distributioner i en strömningsmiljö, men framstegen när det gäller grafproblem har varit begränsade. En huvudorsak till detta har varit förekomsten av linjärt utrymme lägre gränser för även enkla problem som att bestämma anslutenheten av en graf. Men i många nya scenarier som uppstår från sociala och andra interaktionsnätverk är antalet hörn betydligt mindre än antalet kanter. Detta har lett till formuleringen av semistreaming modellen där vi antar att utrymmet är (nära) linjär i antalet hörn (men inte nödvändigtvis kanterna), och kanterna visas i en godtycklig (och möjligen motstående) ordning. Det har dock gjorts begränsade framsteg när det gäller att analysera grafalgoritmer i denna modell. I detta papper fokuserar vi på graf sparifiering, som är en av de viktigaste byggstenarna i en mängd olika grafalgoritmer. Vidare har det funnits en lång historia av (icke-streaming) provtagningsalgoritmer som ger glesa graf approximationer och det är en naturlig fråga att ställa: eftersom slutresultatet av den glesa approximationen är en liten (linjär) rymdstruktur, kan vi uppnå att använda ett litet utrymme, och dessutom använda ett enda pass över data? Frågan är intressant ur både teorins och praktikens synvinkel och vi besvarar frågan jakande, genom att tillhandahålla en en pass Õ (n/ på 2 ) rymdalgoritm som producerar en sparifiering som approximerar varje skärning till en (1 +  på) faktor. Vi visar också att utrymme är nödvändigt för en one pass streaming algoritm för att approximera min-cut, förbättra på den lägre gränsen som uppstår från lägre gränser för att testa konnektivitet.
I denna inställning, Ahn och Guha REF ge en ett pass Õ (n/ 2 ) utrymme algoritm som sparifierar en graf så att varje snitt är ungefärlig till inom en (1 + ) faktor.
Graph Sparsification in the Semi-streaming Model
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}