2015 | OriginalPaper | Buchkapitel
Faster Fully-Dynamic Minimum Spanning Forest
verfasst von : Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen
Erschienen in: Algorithms - ESA 2015
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 give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in
O
(log
4
n
/loglog
n
) expected amortized time per operation, improving the
O
(log
4
n
) amortized bound of Holm et al. (STOC ’98, JACM ’01). We also provide a deterministic data structure with amortized update time
O
(log
4
n
logloglog
n
/loglog
n
). We assume the Word-RAM model with standard instructions.