Vi initierar studien av grafskissering, d.v.s. algoritmer som använder ett begränsat antal linjära mätningar av en graf för att bestämma grafens egenskaper. Medan en graf på n noder är väsentligen O(n 2 )-dimensionell, visar vi förekomsten av en fördelning över slumpmässiga projektioner i d-dimensionella "sketch" utrymme (d « n 2 ) sådan att flera relevanta egenskaper hos den ursprungliga grafen kan härledas från skissen med hög sannolikhet. Specifikt visar vi att: 1. d=O(n · polylog n) räcker för att utvärdera egenskaper inklusive konnektivitet, k-konnektivitet, bipartitet, och för att returnera varje konstant approximation av vikten av minsta spanning träd. 2. d=O(n 1+γ ) räcker för att beräkna grafen sparifierare, den exakta MST, och ungefärliga den maximala viktade matchningar om vi tillåter O(1/γ)-runda adaptiva skisser, dvs en sekvens av projektioner där varje projektion kan väljas beroende på resultatet av tidigare skisser. Våra resultat har två huvudsakliga tillämpningar, vilka båda har potential att ge upphov till fruktbara linjer för ytterligare forskning. Först kan vi tänka oss att våra resultat ger de första komprimerade stilalgoritmerna för grafdata. För det andra inleder vårt arbete studiet av dynamiska grafströmmar. Det finns redan omfattande litteratur om bearbetning av massiva grafer i dataströmsmodellen. Det befintliga arbetet fokuserar dock på grafer som definieras av en sekvens av infogade kanter och tar inte hänsyn till kantraderingar.Vi tycker att detta är ett märkligt utelämnande med tanke på det befintliga arbetet med både dynamiska grafer i icke-strömningsinställningen och dynamisk geometrisk strömning. Våra resultat inkluderar den första dynamiska graf semi-streaming algoritmer för anslutning, spännvidd träd, sparifiering, och matchande problem.  Vi initierar studien av grafskissering, d.v.s. algoritmer som använder ett begränsat antal linjära mätningar av en graf för att bestämma grafens egenskaper. Medan en graf på n noder är väsentligen O(n 2 )-dimensionell, visar vi förekomsten av en fördelning över slumpmässiga projektioner i d-dimensionella "sketch" utrymme (d n 2 ) sådan att flera relevanta egenskaper hos den ursprungliga grafen kan härledas från skissen med hög sannolikhet. Specifikt visar vi att: 1. d = O(n · polylog n) räcker för att utvärdera egenskaper inklusive konnektivitet, k-konnektivitet, bipartitet, och för att returnera varje konstant approximation av vikten av minsta spanning träd. 2. d = O(n 1+γ ) räcker för att beräkna grafen sparifierare, den exakta MST, och ungefärliga den maximala viktade matchningar om vi tillåter O(1/γ)-runda adaptiva skisser, dvs en sekvens av projektioner där varje projektion kan väljas beroende på resultatet av tidigare skisser. Våra resultat har två huvudsakliga tillämpningar, vilka båda har potential att ge upphov till fruktbara linjer för ytterligare forskning. Först kan vi tänka oss att våra resultat ger de första komprimerade stilalgoritmerna för grafdata. För det andra inleder vårt arbete studiet av dynamiska grafströmmar. Det finns redan omfattande litteratur om bearbetning av massiva grafer i dataströmsmodellen. Det befintliga arbetet fokuserar dock på grafer som definieras av en sekvens av infogade kanter och tar inte hänsyn till kantraderingar. Vi tycker att detta är ett märkligt utelämnande med tanke på det befintliga arbetet med både dynamiska grafer i non-streaming-inställningen och dynamisk geometrisk streaming. Våra resultat inkluderar den första dynamiska graf semi-streaming algoritmer för anslutning, spännvidd träd, sparifiering, och matchande problem.
Ahn och Al. REF initierade studien av grafskisser, och gav dynamiska semi-streaming algoritmer för beräkning av en spännande skog (som kan användas för att räkna det exakta antalet anslutna komponenter), och (1 + ε)-ungefärlig vikt MST.
Analyzing Graph Structure via Linear Measurements
{'venue': 'Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms', 'journal': 'Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms', 'mag_field_of_study': ['Computer Science']}