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. Detta papper tar hänsyn till bredd-första sökning (BFS) spänner träd, och tar itu med problemet med att utforma ett glest fel-tolerant BFS träd, eller FT-BFS träd för kort, nämligen en gles delgraf T i det givna nätverket G sådan att efter misslyckandet med en enda kant eller vertex, den överlevande delen T av T fortfarande innehåller en BFS spanning träd för (den överlevande delen av) G. För en källa nod s, en mål nod t och en kant e G, den kortaste s - t sökväg P s,t,e som inte går igenom e är känd som en ersättning väg. På så sätt innehåller vårt FT-BFS-träd insamling av alla utbytesvägar P s,t,e för varje t V (G) och varje misslyckad kant e  på E(G). Våra viktigaste resultat är följande. Vi presenterar en algoritm som för varje n-vertex graf G och källa nod s konstruerar en (single edge fel) FT-BFS träd rotade på s med O(n · min {Depth(s), ε n}) kanter, där Djup (s) är djupet av BFS träd rotade på s. Detta resultat kompletteras med en matchande nedre gräns, visar att det finns n-vertex grafer med en källa nod s för vilka någon kant (eller vertex) FT-BFS träd rotade vid s har  och att det finns n-vertex grafer med en källa nod s för vilka någon kant (eller vertex) FT-BFS kanter. Vi anser sedan feltoleranta multi-källa BFS träd, eller FT-MBFS träd för kort, syftar till att ge (efter ett misslyckande) ett BFS träd rotade vid varje källa s. S för vissa delmängd av källor S  på V. Återigen, snäva gränser tillhandahålls, visar att det finns en poly-tid algoritm som för varje n-vertex graf och källa som S  på storleksskalan V konstruerar en (enkelt misslyckande) FT-MBFS träd T * (S) från varje källa s i S, med O ( ε σ · n 3/2 ) kanter, och å andra sidan finns det n-vertex diagram med källkodsuppsättningar S  och V kardinalitet σ, på vilka alla FT-MBFS träd från S har  och N 3/2 ) kanter. Slutligen föreslår vi en O(log n) approximationsalgoritm för konstruktion av FT-BFS- och FT-MBFS-strukturer. Den senare kompletteras med ett hårdhetsresultat som anger att det inte finns någon approximationsalgoritm för dessa problem enligt standardiserade komplexa antaganden. I jämförelse med den randomiserade FT-BFS konstruktion implicit i [14], är vår algoritm deterministisk och kan förbättra antalet kanter genom en faktor upp till ε n för vissa fall. Alla våra algoritmer kan utökas för att hantera en vertex fel också, med samma prestanda.
Parter och Peleg REF utformade en algoritm för att beräkna enstaka fel tolerant BFS träd med O(n 3/2 ) utrymme.
Sparse Fault-Tolerant BFS Trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}