I 1999, Brodal och Fagerberg (BF) gav en algoritm för att upprätthålla en låg utgrad orientering av en dynamisk jämnt gles graf. Specifikt, för en dynamisk graf på n-vertices, med Arboricity begränsas av α hela tiden, stöder BF algoritm kantuppdateringar i O(log n) amortized uppdateringstid, samtidigt som den maximala utgradera i grafen begränsas av O(α). En sådan orientering ger en grundläggande datastruktur för jämnt glesa grafer, som fann tillämpningar till en uppsjö av dynamiska grafalgoritmer. En betydande svaghet i BF-algoritmen är den möjliga tillfälliga uppblåsningen av maximal utgradering, efter kantinsättningar. Även om BF så småningom minskar alla utgrader till O(α), vissa hörn kan nå en utgradera av (n) under processen, därav lokal minnesanvändning vid hörn-en viktig kvalitetsmått i distribuerade system-kan inte begränsas. Vi visar hur man modifierar BF algoritmen för att garantera att utgrader av alla hörn begränsas av O(α) hela tiden, utan att skada någon av dess andra egenskaper, och presentera en effektiv distribuerad implementering av den modifierade algoritmen. Detta ger den första representationen av distribuerade nätverk där den lokala minnesanvändningen på hörn avgränsas av arboricity (som i huvudsak är den genomsnittliga graden av den tätaste subgrafen) snarare än den maximala graden. För inställningar där det inte finns några lokala minnesbegränsningar, kan man ta den tillfälliga utgradera blåsningen till extrem och tillåta en permanent utgradera blåsning. Detta gör att vi kan ta itu med den andra betydande svagheten i BF algoritm - dess inneboende globala natur: En insättning av en kant (u, v) kan utlösa förändringar i inriktningen av kanter som är godtyckligt långt från u och v. Vi föreslår ett alternativt lokalt system, som inte garanterar någon utexamen bundna på hörnen, men är ändå lika effektivt som BF systemet för vissa tillämpningar. Till exempel får vi en lokal dynamisk algoritm för att upprätthålla en maximal matchning med sublogaritmisk uppdateringstid i enhetligt glesa nätverk, vilket ger en exponentiell förbättring jämfört med toppmoderna i detta sammanhang.
Kaplan och Solomon REF visade hur man behåller kantorienteringar i den distribuerade inställningen när det lokala minnet per nod är begränsat.
Dynamic Representations of Sparse Distributed Networks: A Locality-Sensitive Approach
{'venue': "SPAA '18", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}