Abstrakt. Computing all best swap kanter (ABSE) av ett spännträd T av en given n-vertex och m-kant oriktad och viktad graf G innebär att välja, för varje kant e av T, en motsvarande icke-träd kant f, på ett sådant sätt att trädet erhålls genom att ersätta e med f har någon optimalitetskriterium (som naturligt definieras enligt någon objektiv funktion som ursprungligen behandlas av T ). Att effektivt lösa ett ABSE-problem är vid det här laget en klassisk algoritmisk fråga, eftersom det förmedlar ett mycket framgångsrikt sätt att hantera ett (övergående) kantfel i trädbaserade kommunikationsnät: ersätt bara den felande kanten med dess respektive swap edge, så att anslutningen snabbt återställs genom att minimera omboknings- och installationskostnaderna. I detta dokument löser vi ABSE-problemet för det fall där T är en enda källa kortaste vägen träd av G, och våra två utvalda swap kriterier syftar till att minimera antingen den maximala eller genomsnittliga sträcka i swapträdet av alla stigar som utgår från källan. Med dessa kriterier i åtanke, kan de erhållna strukturerna sedan ses över som kant-fel-toleranta en källa skiftnycklar. För dem föreslår vi två effektiva algoritmer som körs i O(mn + n 2 log n) och O(mn log α(m, n)) tid, respektive, och vi visar att den garanterade (antingen maximal eller genomsnittlig, respektive) stretch faktor är lika med 3, och detta är tight. För den maximala sträckan föreslår vi dessutom en nästan linjär tidsalgoritm för O(m log α(m, n) som beräknar en uppsättning bra swapkanter, som var och en kommer att garantera en relativ approximationsfaktor för den maximala sträckan på 3/2 (tight) jämfört med den som tillhandahålls av motsvarande BSE. Förvånansvärt nog var inga tidigare resultat kända för dessa två mycket naturliga swapproblem.
Nyligen föreslog författarna i Ref två nya kriterier för swaping i en SPT, som på sätt och vis är relaterade till detta dokument, nämligen minimering av den maximala och genomsnittliga stretchfaktorn från roten, för vilken de föreslog en effektiv O(mn + n 2 log n) respektive O(mn log α(m, n)) tidslösning.
Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}