Låt G = (V, E) vara en graf med n hörn och m kanter, med en angiven uppsättning av σ källor S. Feltolerant subgraf för alla graf problem upprätthåller en gles subgraf H = (V, E ′ ) av G med E, så att för varje uppsättning F av k misslyckanden, lösningen för grafen problem på G \ F upprätthålls i dess subgraf H \ F. Vi tar itu med problemet med att upprätthålla ett fel tolerant subgraph för beräkning Breath First Search Tree (BFS) av grafen från en enda källa s  på V (kallas k FT-BFS) eller flera källor S  på V (kallas k-MBFS). Vi hänvisar helt enkelt till dem som FT-BFS (eller FT-MBFS) för k = 1, och dubbla FT-BFS (eller dubbla FT-MBFS) för k = 2. Problemet med k FT- BFS undersöktes först av Parter och Peleg [ESA13]. De utformade en algoritm för att beräkna FT-BFS subgraph i storlek O(n 3/2 ). Vidare visade de hur deras algoritm enkelt kan utökas till FT-MBFS kräver O(σ 1/2 n 3/2 ) utrymme. De presenterade också matchande lägre gränser för dessa resultat. Resultatet utvidgades senare för att lösa dubbla FT-BFS av Parter [PODC15] kräver O(n 5/3 ) utrymme, återigen med matchande nedre gränser. Deras resultat var dock begränsat till endast kantfel i oriktade grafer och innebar en mycket komplex analys. Dessutom verkar deras lösning inte vara direkt förlängningsbar för dubbla FT-MBFS-problem. Vi presenterar en liknande algoritm för att lösa dubbla FT-BFS-problem med en mycket enklare analys. Dessutom fungerar vår algoritm också för vertex fel och riktade grafer, och kan enkelt utökas för att hantera dubbla FT-MBFS-problem, matchar den nedre gränsen av O(σ 1/3 n 5/3 ) utrymme beskrivs av Parter [PODC15]. Den viktigaste skillnaden i vårt tillvägagångssätt är en mycket enklare klassificering av väginteraktioner som utgjorde grunden för analysen av Parter [PODC15]. Vår dubbla FT-MBFS struktur ger också sömlöst en dubbel feltolerant skiftnyckel med additiv stretch på +2 med storlek O(n-7 ).
Gupta och Khan REF utvidgade ovanstående resultat till flera källor med O(σ 1/3 n 5/3 ) utrymme.
Multiple Source Dual Fault Tolerant BFS Trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}