Advertisement
Published in:
2005 | OriginalPaper | Chapter
Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a deterministic algorithm for computing the
sensitivity
of a minimum spanning tree or shortest path tree in
O
(
m
log
α
(
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.