Låt G vara en n-node och m-kant positivt real-viktad oriktad graf. För varje givet heltal f ≥ 1, studerar vi problemet med att utforma en sparse f-edge-fault-tolerant (f -EFT) σ-ungefärlig en källa kortaste vägen träd (σ-ASPT), nämligen en del av G har så få kanter som möjligt och som, efter misslyckandet med en uppsättning F på de flesta f kanter i G, innehåller vägar från en fast källa som sträcks som mest av en faktor av σ. I detta avseende tillhandahåller vi en algoritm som på ett effektivt sätt beräknar en f-EFT (två gånger F) + 1)-ASPT i storlek O (f n). Vår struktur förbättrar en tidigare relaterad konstruktion utformad för oviktade grafer, med samma storlek men garanterar en större stretchfaktor på 3 f + 1), plus en additiv term av (f + 1) log n. Därefter visar vi hur man konverterar vår struktur till en effektiv f -EFT en källa avstånd oracle (SSDO), som kan byggas i O (f m) tid, har storlek O (f n log 2 n), och kan rapportera, efter misslyckandet med kanten som F, i O (  och F) 2 log 2 n) tid a (2 och F + 1)-ungefärlig avstånd från källan till någon nod, och en motsvarande ungefärlig väg i samma tid plus banans storlek. Ett sådant orakle erhålls genom att hantera ett annat grundläggande problem, nämligen att uppdatera en minsta spännskog (MSF) av G efter att ett parti av k samtidiga kantmodifieringar (dvs. kantinsättningar, raderingar och viktförändringar) utförs. För detta problem, vi bygger i O(m log 3 n) tid en känslighet oracle av storlek O (m log 2 n), som rapporterar i O(k 2 log 2 n) tid (som mest 2k) kanter antingen lämna eller gå in i MSF. Som ett resultat av oberoende intresse, är det värt att notera att vår MSF oracle kan användas för att hantera godtyckliga sekvenser av o( 4 ε n/ log n) (icke-simultana) uppdateringar med en värsta fall tid per uppdatering av o( ε n). Således, för relativt korta sekvenser av uppdateringar, bör vårt orakel föredras w.r.t. Den mest kända (i värsta fall) MSF-algoritm som är helt dynamisk och som kräver O ( ε n) tid per uppdatering.
I ett annat resultat, Bilò et. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. REF utformade en k feltolerant avstånd oracle av storlek Õ (kn) med en sträcka faktor (2k + 1) som kan svara på frågor i Õ (k 2 ) tid.
Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}