Sammanfattning Låt G vara en graf med n hörn och m kanter. En glesare G är en gles graf på samma vertex som ungefärlig G på något naturligt sätt. Det gör att vi kan säga användbara saker om G samtidigt med tanke på mycket mindre än m kanter. Den starkaste allmänt använda uppfattningen om sparifiering är spektral sparifiering; H är en spektral sparifierare av G om de kvadratiska former som induceras av Laplacians av G och H approximerar varandra väl. Detta begrepp är mycket starkare än det tidigare begreppet kombinatorisk sparifiering. I detta dokument överväger vi en semi-streaming inställning, där vi bara har Õ(n) lagringsutrymme, och vi kan därför inte behålla hela G. I detta fall, underhåll av en sparfier i stället ger oss en användbar approximation till G, så att vi kan svara på vissa frågor om den ursprungliga grafen utan att lagra allt. Vi introducerar en algoritm för att bygga en spektral sparifierare av G med O(n log n/ 2 ) kanter (där är en parameter som mäter kvaliteten på sparifieraren), tar Õ(m) tid och kräver endast en passera över G. Dessutom har vår algoritm den egenskap som den upprätthåller hela tiden en giltig sparifierare för subgrafen av G som vi har fått. Vår algoritm är naturlig och konceptuellt enkel. När vi läser kanter av G, lägger vi dem till sparifieraren H. När H blir för stor, vi justerar det i Õ(n) tid. Lägga till kanter i en graf ändrar strukturen på dess sparifierarens begränsning till de redan befintliga kanterna. Det verkar alltså som om ovanstående förfarande skulle leda till att fel kompliceras varje gång vi omsparsifierar, och att vi antingen måste behålla betydligt mer information eller ompröva tidigare kasserade kanter för att konstruera den nya sparifieraren. Vi visar dock hur man använder informationen i H för att utföra denna omräkning med hjälp av endast de kanter som behållits av tidigare steg i nästan linjär tid.
Kelner och Levin REF producerar en spektral glesare med O(n log n/ 2 ) kanter i Õ(m) tid.
Spectral Sparsification in the Semi-streaming Setting
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Mathematics', 'Computer Science']}