Geodesic
Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 375-391.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We present a deterministic algorithm for computing the sensitivity of a minimum spanning tree (MST) or shortest path tree in O(mlogα(m,n)) time, where α is the inverse-Ackermann function. This improves upon a long standing bound of O(mα(m,n)) established by Tarjan. Our algorithms are based on an efficient split-findmin data structure, which maintains a collection of sequences of weighted elements that may be split into smaller subsequences. As far as we are aware, our split-findmin algorithm is the first with superlinear but sub-inverse-Ackermann complexity. We also give a reduction from MST sensitivity to the MST problem itself. Together with the randomized linear time MST algorithm of Karger, Klein, and Tarjan, this gives another randomized linear time MST sensitivity algorithm. 
@article{JGAA_2015_19_1_a18,
     author = {Seth Pettie},
     title = {Sensitivity {Analysis} of {Minimum} {Spanning} {Trees} in {Sub-Inverse-Ackermann} {Time}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {375--391},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00365},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00365/}
}
TY  - JOUR
AU  - Seth Pettie
TI  - Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 375
EP  - 391
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00365/
DO  - 10.7155/jgaa.00365
LA  - en
ID  - JGAA_2015_19_1_a18
ER  - 
%0 Journal Article
%A Seth Pettie
%T Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
%J Journal of Graph Algorithms and Applications
%D 2015
%P 375-391
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00365/
%R 10.7155/jgaa.00365
%G en
%F JGAA_2015_19_1_a18
Seth Pettie. Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 375-391. doi : 10.7155/jgaa.00365. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00365/

Cité par Sources :