Faster Fully-Dynamic minimum spanning forest

Jacob Holm; Eva Rotenberg; Christian Wulff-Nilsen

doi:10.1007/978-3-662-48350-3_62

Faster Fully-Dynamic minimum spanning forest

Jacob Holm
, Eva Rotenberg
, Christian Wulff-Nilsen

Department of Applied Mathematics and Computer Science

University of Copenhagen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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(log⁴ n/log logn) expected amortized time per operation, improving the O(log⁴ n) amortized bound of Holm et al. (STOC’98, JACM’01).We also provide a deterministic data structure with amortized update time O(log⁴ nlogloglogn/log logn). We assume the Word-RAM model with standard instructions.

Original language	English
Title of host publication	Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
Number of pages	12
Volume	9294
Publisher	Springer Verlag
Publication date	2015
Pages	742-753
ISBN (Print)	9783662483497
DOIs	https://doi.org/10.1007/978-3-662-48350-3_62
Publication status	Published - 2015
Event	23rd European Symposium on Algorithms - Patras, Greece Duration: 14 Sept 2015 → 16 Sept 2015 Conference number: 23 http://algo2015.upatras.gr/esa/

Conference

Conference	23rd European Symposium on Algorithms
Number	23
Country/Territory	Greece
City	Patras
Period	14/09/2015 → 16/09/2015
Internet address	http://algo2015.upatras.gr/esa/

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9294
ISSN	0302-9743

Access to Document

10.1007/978-3-662-48350-3_62

OpenUrl availability

Full text

Cite this

@inproceedings{f39617f4d20941cd87482ae0852667f6,

title = "Faster Fully-Dynamic minimum spanning forest",

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{\textquoteright}98, JACM{\textquoteright}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.",

author = "Jacob Holm and Eva Rotenberg and Christian Wulff-Nilsen",

year = "2015",

doi = "10.1007/978-3-662-48350-3\_62",

language = "English",

isbn = "9783662483497",

volume = "9294",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "742--753",

booktitle = "Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings",

address = "Germany",

note = "23rd European Symposium on Algorithms, ESA 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

url = "http://algo2015.upatras.gr/esa/",

}

Holm, J, Rotenberg, E & Wulff-Nilsen, C 2015, Faster Fully-Dynamic minimum spanning forest. in Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. vol. 9294, Springer Verlag, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9294, pp. 742-753, 23rd European Symposium on Algorithms, Patras, Greece, 14/09/2015. https://doi.org/10.1007/978-3-662-48350-3_62

Faster Fully-Dynamic minimum spanning forest. / Holm, Jacob; Rotenberg, Eva; Wulff-Nilsen, Christian.
Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Vol. 9294 Springer Verlag, 2015. p. 742-753 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9294).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Faster Fully-Dynamic minimum spanning forest

AU - Holm, Jacob

AU - Rotenberg, Eva

AU - Wulff-Nilsen, Christian

N1 - Conference code: 23

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84945535380

U2 - 10.1007/978-3-662-48350-3_62

DO - 10.1007/978-3-662-48350-3_62

M3 - Article in proceedings

AN - SCOPUS:84945535380

SN - 9783662483497

VL - 9294

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 742

EP - 753

BT - Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 23rd European Symposium on Algorithms

Y2 - 14 September 2015 through 16 September 2015

ER -

Holm J, Rotenberg E, Wulff-Nilsen C. Faster Fully-Dynamic minimum spanning forest. In Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Vol. 9294. Springer Verlag. 2015. p. 742-753. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9294). doi: 10.1007/978-3-662-48350-3_62

Faster Fully-Dynamic minimum spanning forest

Abstract

Conference

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this