Dynamisk konnektivitet är ett välstuderat problem, men hittills har de mest övertygande framstegen begränsats till egg-update-modellen: upprätthålla en förståelse för konnektivitet i en oriktad graf, med förbehåll för kantinsättningar och raderingar. I denna uppsats studerar vi två mer utmanande, men lika grundläggande problem: Subgraph konnektivitet ber att upprätthålla en förståelse av konnektivitet under vertex uppdateringar: uppdateringar kan slå hörn på och av, och frågor hänvisar till subgraph framkallas av på hörn. (Detta är till exempel närmare tillämpningar i nätverk av routers, där nodfel kan uppstå.) Vi beskriver en datastruktur som stöder vertex uppdateringar i O(m 2/3 ) amorterad tid, där m betecknar antalet kanter i grafen. Detta förbättras avsevärt jämfört med det tidigare resultatet [Chan, STOC'02], som krävde snabb matris multiplikation och hade en uppdateringstid på O(m 0.94 ). Den nya datastrukturen är också enklare. Geometriska konnektivitet ber om att behålla en dynamisk uppsättning av n geometriska objekt, och fråga konnektivitet i deras skärningskurva. (Till exempel, skärningskurvan av bollar beskriver anslutning i ett nätverk av sensorer med begränsad överföringsradie.) Tidigare var icke-triviala fullt dynamiska resultat kända endast för specialfall som axelparallelllinjesegment och rektanglar. Vi ger på liknande sätt förbättrade uppdateringstider, O(n 2/3 ), för dessa specialfall. Dessutom visar vi hur man får sublinjära uppdateringsgränser för praktiskt taget alla familjer av geometriska objekt som tillåter sublinjära tidsintervall frågor. I synnerhet får vi den första sublinjära uppdateringstiden för godtyckliga 2D-linjesegment: O * (n 9/10 );
I en amorterad inställning, den datastruktur som ges av Chan, Patrascu och Roditty REF har en uppdateringstid Õ(m 2/3 ) och frågestund O(m 1/3 ); dess rymdanvändning och förbehandlingstid är Õ(m 4/3 ).
Dynamic Connectivity: Connecting to Networks and Geometry
{'venue': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}