Vi presenterar en deterministisk algoritm för beräkning av känsligheten hos ett minsta spännträd (MST) eller kortaste stigträd i O(m log α(m, n)) tid, där α är inverse-Ackermann funktion. Detta förbättras vid en långvarig gräns för O(mα(m, n) som fastställts av Tarjan. Våra algoritmer är baserade på en effektiv split-findmin datastruktur, som upprätthåller en samling sekvenser av viktade element som kan delas upp i mindre undersekvenser. Så vitt vi vet är vår split-findmin algoritm den första med superlinjär men sub-invers-Ackermann komplexitet. Vi ger också en minskning av MST-känsligheten för själva MST-problemet. Tillsammans med den randomiserade linjära tidsalgoritmen MST för Karger, Klein och Tarjan ger detta ytterligare en randomiserad linjär tid MST känslighetsalgoritm.
Den mest kända explicita gränsen för deterministiska algoritmer är O(m log α(m, n)), där α(m, n) betecknar en funktionell invers av Ackermann funktionen REF.
Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}