Låt s betecknar en särskiljande källa vertex av en icke-negativt real viktad och oriktad graf G med n hörn och m kanter. I detta dokument presenterar vi två effektiva approximativt avståndskänsliga orakel, nämligen kompakta datastrukturer som snabbt kan rapportera ett ungefärligt (genom en multiplikativ stretchfaktor) avstånd från s till någon nod av G efter fel på någon kant i G. Närmare bestämt presenterar vi först en känslighet orakel av storlek O(n) som kan rapportera 2- approximerade avstånd från källan i O(1) tid. Sedan vidareutvecklar vi vår konstruktion genom att bygga, för alla 0 < ε < 1, en annan känslighet orakel med storlek O n · 1 ε log 1 ε, och som kan rapportera en (1 + ε) - ungefärligt avstånd från s till någon vertex av G i O log n · 1 ε log 1 ε tid. Således är denna senare orakel i huvudsak optimal när det gäller storlek och sträcka, och den ber bara om en logaritmisk frågestund. Slutligen kompletteras våra resultat med ett utrymme lägre bundet för den relaterade klassen av en källa additivt utsträckta sensitiva orakel, vilket är till hjälp för att förverkliga hårdheten i att utforma kompakta orakel av denna typ.
Mycket nyligen, i REF, författarna visar hur man bygger en (icke-vägrapportering) SDSO som har stretch 1 + ε, storlek O (nε) och frågestund O (δ log n), där ε = ε −1 log ε −1, som kan förbättras till O(1) för specialfallet ε = 1.
Compact and Fast Sensitivity Oracles for Single-Source Distances
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}