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 Computer Science

14 Citations (Scopus)

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, Patras, Greece, September 14-16, 2015, Proceedings
Number of pages	12
Publisher	Springer
Publication date	2015
Pages	742-753
Chapter	62
ISBN (Print)	978-3-662-48349-7
ISBN (Electronic)	978-3-662-48350-3
DOIs	https://doi.org/10.1007/978-3-662-48350-3_62
Publication status	Published - 2015
Event	Annual European Symposium 2015 - Patras, Greece Duration: 14 Sept 2015 → 16 Sept 2015 Conference number: 23

Conference

Conference	Annual European Symposium 2015
Number	23
Country/Territory	Greece
City	Patras
Period	14/09/2015 → 16/09/2015

Series	Lecture notes in computer science
Volume	9294
ISSN	0302-9743

Access to Document

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

Cite this

Faster fully-dynamic minimum spanning forest. / Holm, Jacob; Rotenberg, Eva; Wulff-Nilsen, Christian.

Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Springer, 2015. p. 742-753 (Lecture notes in computer science, Vol. 9294).

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

Holm, J, Rotenberg, E & Wulff-Nilsen, C 2015, Faster fully-dynamic minimum spanning forest. in Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Springer, Lecture notes in computer science, vol. 9294, pp. 742-753, Annual European Symposium 2015, Patras, Greece, 14/09/2015. https://doi.org/10.1007/978-3-662-48350-3_62

@inproceedings{cc3e06b8dd3e45378afff7974abd7e18,

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 = "978-3-662-48349-7",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "742--753",

booktitle = "Algorithms - ESA 2015",

note = "Annual European Symposium 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

}

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.

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

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

M3 - Article in proceedings

SN - 978-3-662-48349-7

T3 - Lecture notes in computer science

SP - 742

EP - 753

BT - Algorithms - ESA 2015

PB - Springer

T2 - Annual European Symposium 2015

Y2 - 14 September 2015 through 16 September 2015

ER -

Faster fully-dynamic minimum spanning forest

Abstract

Conference

Access to Document

Fingerprint

Cite this