Vi studerar dynamiska algoritmer för att upprätthålla spektral vertex sparifierare av grafer med avseende på en uppsättning terminaler T som vi väljer. Sådana objekt bevarar parvis motstånd, lösningar till system av linjära ekvationer, och energi av elektriska flöden mellan terminalerna i T. Vi ger en datastruktur som stöder tillägg och raderingar av kanter, och terminala tillägg, allt i sublinjär tid. Vi visar sedan att vårt resultat är tillämpligt på följande problem. (1) En datastruktur för dynamisk underhåll av lösningar till Laplacian systems Lx = b, där L är grafen Laplacian matris och b är en efterfrågan vektor. För en begränsad grad, oviktad graf, stöder vi ändringar av både L och b samtidigt som vi ger tillgång till ε-ungefärande energi routing ett elektriskt flöde med efterfrågan b, samt frågeåtkomst till poster i en vektorx sådan att förväntade amortized uppdatering och frågetid. (2) En datastruktur för att upprätthålla fullt dynamisk All-Pairs Effektiv Resistance. För en blandad sekvens av kantinsättningar, raderingar och motståndsförfrågningar återgår våra datastrukturer (1 ± ε) till alla motståndsförfrågningar mot en omedveten motståndare med hög sannolikhet. Dess förväntade amorterade uppdaterings- och frågetider är Õ(min(m 3/4, n 5/6 ε −2 )ε −4 ) på en oviktad graf och Õ(n 5/6 ε −6 ) på viktade grafer. De viktigaste ingredienserna i dessa resultat är (1) intepretation av Schur komplement som en summa av slumpmässiga promenader, och (2) ett lämpligt val av terminaler baserat på beteendet hos dessa slumpmässiga promenader för att se till att majoriteten av promenader är lokala, även när grafen själv är mycket ansluten och (3) underhåll av dessa lokala promenader och numeriska lösningar med hjälp av datastrukturer. Dessa resultat representerar tillsammans de första datastrukturerna för att upprätthålla viktiga primitiver från Laplacians paradigm för grafalgoritmer i sublinjär tid utan antaganden om de underliggande graftopologierna. Vikten av rutiner som effektivt motstånd, elektriska flöden och laplaciska lösare i den statiska miljön gör oss optimistiska om att vissa av våra komponenter kan ge nya byggstenar för dynamiska grafalgoritmer. • Teori för beräkning → Dynamiska grafalgoritmer.
För underhåll (1 + ) - approximationer till alla-par effektiva motstånd av en fullt dynamisk graf, REF gav en datastruktur vars förväntade amortized uppdatering och frågetider är O(min(m 3/4, n 5/6 −2 ) −4 ) på en oviktad graf, och O(n 5/6 −6 ) på viktade grafer.
Fully dynamic spectral vertex sparsifiers and applications
{'venue': 'STOC 2019', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}