Faster Fully-Dynamic minimum spanning forest

Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in O(log4 n/log logn) expected amortized time per operation, improving the O(log4 n) amortized bound of Holm et al. (STOC’98, JACM’01).We also provide a deterministic data structure with amortized update time O(log4 nlogloglogn/log logn). We assume the Word-RAM model with standard instructions.

Original languageEnglish
Title of host publicationAlgorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
Number of pages12
Volume9294
PublisherSpringer Verlag
Publication date2015
Pages742-753
ISBN (Print)9783662483497
DOIs
Publication statusPublished - 2015
Event23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece
Duration: 14 Sep 201516 Sep 2015

Conference

Conference23rd European Symposium on Algorithms, ESA 2015
CountryGreece
CityPatras
Period14/09/201516/09/2015
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9294
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Faster Fully-Dynamic minimum spanning forest'. Together they form a unique fingerprint.

Cite this