Ett träd σ-spanner av en positivt real-viktad n-vertex och m-kant oriktad graf G är ett spännträd T av G som ungefär bevarar (dvs upp till en multiplikativ stretchfaktor σ) avstånd i G. Träd spannare med bevisbart bra stretch faktorer hitta tillämpningar i kommunikationsnät, distribuerade system och nätverksdesign. Men att hitta en optimal eller till och med en bra trädspännare är en mycket svår beräkningsuppgift. Således, om man måste möta en övergående kant fel i T, den totala ansträngning som måste ges för att återuppbygga en ny träd skiftnyckel (dvs., beräkningskostnader, uppsättning av nya länkar, uppdatering av routing tabeller, etc.) kan vara ganska oöverkomlig. För att kringgå denna nackdel, ett effektivt alternativ är att associera med varje trädkant en bästa möjliga (i termer av resulterande stretch) swap edge - ett väletablerat tillvägagångssätt i litteraturen för flera andra träd topologier. På motsvarande sätt, problemet med att beräkna alla de bästa swap kanterna på ett träd skiftnyckel är ett utmanande algoritmiskt problem, eftersom lösa det effektivt innebär att utnyttja strukturen på kortaste vägar inte bara i G, men också i alla scenarier där en kant av T har misslyckats. För detta problem ger vi en mycket effektiv lösning, kör i O(n 2 log 4 n) tid, vilket drastiskt förbättrar (nästan genom en kvadratisk faktor i n i täta grafer!) på det tidigare kända bästa resultatet. Nyckelord och fraser Transient edge failure, Swap algoritm, Tree skiftnyckel Problemet med att beräkna alla de bästa swap kanter (ABSE) av ett träd har en lång och rik algoritmisk tradition. I grund och botten, låt G = (V (G), E(G), w) vara en n-vertex och m-kanten 2-kantsansluten oriktad graf, med egg-vikt funktion w : E(G) → R +, och anta att vi får en spännvidd träd T av G, som beräknades genom att ta itu med vissa kriterium (dvs. objektiv funktion). Sedan, problemet är att beräkna en BSE för varje kant e E(T ), nämligen en kant f  på E(G) \ E(T ) så att byte träd T e/f erhålls genom att byta e med f i T optimerar någon objektiv funktion av alla möjliga byte träd. Ganska rimligt, funktionen måste vara relaterad (om inte sammanfalla alls) med  på. Den första omedelbara motivationen för att studera ett ABSE problem kommer från kanten feltolerans inställning - ett allmänt accepterat ramverk. I stort sett är den algoritmiska frågan här att utforma glesa subgrafer som garanterar en lämplig nivå av funktionalitet även i närvaro av ett kantfel. I ett sådant sammanhang är syftet med en ABSE-baserad lösning följande: verksamheten utförs normalt på en (eventuellt optimal) spännvidd
Nyligen, i REF författarna utformade en mycket smart rekursiv algoritm som använder centroid-dekomposition tekniker och lägre kuvert datastrukturer för att lösa ABSE-problemet på träd spannare i O(n 2 log 4 n) tid och O(n 2 + m log 2 n) utrymme.
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}