2005 | OriginalPaper | Buchkapitel
Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time
verfasst von : Seth Pettie
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.