Vi undersöker problemet med en enda länk fel återvinning och dess tillämpning på alternativa vägen routing problem för ATM-nätverk, och k-ersättning kanter för varje kant av en minsta kostnad spänna träd. Speciellt, med tanke på en 2-ansluten graf G, en specificerad nod s, och en kortaste stigar träd Ts = {e1, e2,. ., en- 1} av s, där ei = (xi, yi) och xi = parentes s (yi), hitta en kortaste vägen från yi till s i grafen G\ei för 1 ≤ i ≤ n − 1. Vi presenterar en O(m + n log n) tid algoritm för detta problem och en linjär tid algoritm för fallet när alla vikter är lika. När kantvikterna är heltal presenterar vi en algoritm som tar O(m + Tsort(n) tid, där Tsort(n) är den tid som krävs för att sortera n heltal. Vi etablerar en lägre gräns för min (m ε n, n 2 ) för den riktade versionen av vårt problem under vägen jämförelse modell, där Ts är de kortaste vägar destination träd av s. Vi visar att någon lösning på den enda länk återhämtning problem kan anpassas för att lösa alternativ väg routing problem i ATM-nätverk. Vår teknik för den enda länk fel återvinning problem är anpassad för att hitta k-ersättning kanter för trädkanterna av en minsta kostnad spänna träd i O (m + n log n) tid.
En snabbare algoritm, med en körtid på O(m + n log n) för detta problem presenterades i REF.
Algorithms for Single Link Failure Recovery and Related Problems
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}