En feltolerant struktur för ett nätverk krävs för att fortsätta fungera efter fel på vissa av nätverkets kanter eller hörn. Denna artikel tar upp problemet med att utforma en feltolerant (α, β ) ungefärlig BFS struktur (eller FT-ABFS struktur för kort), nämligen, en delgraf H i nätverket G sådan att efter misslyckandet för vissa delmängd F av kanter eller hörn, den överlevande delen av H (nämligen, H\ F ) fortfarande innehåller en ungefärlig BFS spanning träd för (den överlevande delen av) G, Vårt första resultat är en algoritm som ges en n-vertex ovägd oriktad graf G och en källa s konstruerar en multiplicativ (3, 0) FT-ABFS struktur rotad på s motståndskraftig mot ett fel på en enda kant med de flesta 4n kanter (bevisa av en O (log n) faktor på den nära-täta resultatet av Baswana och Khanna (2010) för speciella fall av kantfel). Detta förbättrades nyligen till 2n kanter av Bilò et al. (2014)................................................................ Därefter anser vi att flera kant fel fall, för ett konstant heltal f > 1, vi bevisar att det finns en (polynom-tid konstruktör) (3f, f log n) FT-ABFS struktur med O ( f n) kanter som är motståndskraftig mot f fel. Vi visar också förekomsten av a (3f + 1, 0) FT-ABFS struktur med O (f log f n · n) kanter. Vi anser sedan additiv (1, β ) FT-ABFS strukturer och visa en intressant dikotomi mellan multiplikativa och additiva skiftnycklar. I motsats till den linjära storleken av (α, 0) FT-ABFS strukturer, visar vi att för varje n finns det δ, ε > 0, och n-vertex grafer G med en källa s för vilka någon (1, n δ ) FT-ABFS struktur rotad vid s har (n 7/6−ε ) kanter. När det gäller additiv stretch 3 visar vi att (1, 3) FT-ABFS strukturer medger en nedre gräns av 5/4 ) kanter.
Parter och Peleg visade i REF en lägre gräns för kanter för en källa FT β-additiva spännen (n 1+ε β ).
Fault-Tolerant Approximate BFS Structures
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}