Preservers och additive spanners är sparsamma (därför billigt att lagra) subgraphs som bevarar avstånden mellan givna par av noder exakt eller med några små additivt fel, respektive. Eftersom verkliga nätverk är benägna att misslyckas, är det vettigt att studera feltoleranta versioner av ovanstående strukturer. Detta visar sig vara en förvånansvärt svår uppgift. För varje liten men godtycklig uppsättning av kant eller vertex misslyckanden, måste bevarare och skiftnycklar innehålla ersättningsvägar runt den felaktiga uppsättningen. Tyvärr exploderar komplexiteten i samspelet mellan ersättningsvägarna avsevärt, även från 1 till 2 fel, och strukturen på optimala skyddsanordningar och skiftnycklar är dåligt förstådd. I synnerhet är inga nontriviala gränser för konserveringsmedel och additiva skiftnycklar kända när antalet fel är större än 2. Till och med svaret på följande oskyldiga fråga är helt okänt: vilken är den värsta storleken på en skyddare för ett enda par noder i närvaro av fel på f edge? Det finns inga superlinjära nedre gränser, inte heller subquadratiska övre gränser för f > 2. I detta dokument gör vi betydande framsteg i denna och andra grundläggande frågor: • Vi presenterar den första verkligt sub-kvadratiska storlek en-par bevarare i oviktade (eventuellt riktade) grafer för varje fast antal f fel. Vårt resultat generaliseras verkligen till en källa fallet, och kan användas för att bygga nya feltoleranta additiv skiftnycklar (för alla par). • Storleken på ovanstående enparsbevarare är O(n 2‐g(f) ) för vissa positiva funktion g, och växer till O(n 2 ) för att öka f. Vi visar att detta är nödvändigt även i oriktade oviktade grafer, och även om du tillåter en liten additiv fel: Om du siktar på storlek O(n 2‐ε ) för ε > 0, då additivt fel måste vara  och även om du tillåter en liten additiv fel. Detta stämmer förvånansvärt väl överens med de kända övre gränserna i litteraturen. • För viktade grafer tillhandahåller vi matchande övre och nedre gränser för ett par fallet. Nämligen är storleken på reservatet (n 2 ) för f ≥ 2 i både riktade och oriktade grafer, medan för f = 1 är storleken (n) i oriktade grafer. För riktade grafer har vi en superlinjär övre gräns och en matchande nedre gräns. De flesta av våra nedre gränser sträcker sig till avståndet orakel inställning, där snarare än en subgraf vi ber om någon kompakt datastruktur.
Mycket nyligen, för alla fasta k ≥ 1, konstruktion av en sub-kvadratisk storlek 2-additiv spännare motståndskraftig mot k kant eller vertex fel har visats för oviktade oriktade grafer REF.
Preserving Distances in Very Faulty Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}