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

Datalogisk Institut

14 Citationer (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.

Originalsprog	Engelsk
Titel	Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings
Antal sider	12
Forlag	Springer
Publikationsdato	2015
Sider	742-753
Kapitel	62
ISBN (Trykt)	978-3-662-48349-7
ISBN (Elektronisk)	978-3-662-48350-3
DOI	https://doi.org/10.1007/978-3-662-48350-3_62
Status	Udgivet - 2015
Begivenhed	Annual European Symposium 2015 - Patras, Grækenland Varighed: 14 sep. 2015 → 16 sep. 2015 Konferencens nummer: 23

Konference

Konference	Annual European Symposium 2015
Nummer	23
Land/Område	Grækenland
By	Patras
Periode	14/09/2015 → 16/09/2015

Navn	Lecture notes in computer science
Vol/bind	9294
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

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. s. 742-753 (Lecture notes in computer science, Bind 9294).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Holm, J, Rotenberg, E & Wulff-Nilsen, C 2015, Faster fully-dynamic minimum spanning forest. i Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Springer, Lecture notes in computer science, bind 9294, s. 742-753, Annual European Symposium 2015, Patras, Grækenland, 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater