Dynamic bridge-finding in õ(log2 n) amortized time

Jacob Holm, Eva Rotenberg, Mikkel Thorup

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

131 Downloads (Pure)

Abstract

We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ((log n)2) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in O(log n/ log log n) worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to log log n factors.
The previous best dynamic bridge finding was an Õ((log n)3) amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the O((log n)4) amortized time algorithm by Holm et al.[STOC98, JACM2001].
Our approach is based on a different and purely combinatorial improvement of the algorithim of Holm et al., which by itself gives a new combinatorial Õ((log n)3) amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed Õ((log n)2) amortized time.
Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to Õ((log n)3).
We also offer improvements in space. We describe a general trick which applies to both of our new algorithms, and to the old ones, to get down to linear space, where the previous best use O(m + n log n log log n).
Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSociety for Industrial and Applied Mathematics
Publication date2018
Pages35-52
ISBN (Electronic)978-1-61197-503-1
Publication statusPublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaze, New Orleans French Quarter , New Orleans , United States
Duration: 7 Jan 201810 Jan 2018
Conference number: 29

Conference

Conference29th Annual ACM-SIAM Symposium on Discrete Algorithms
Number29
LocationAstor Crowne Plaze, New Orleans French Quarter
CountryUnited States
CityNew Orleans
Period07/01/201810/01/2018
SeriesProceedings of the Twenty-ninth Annual Acm-siam Symposium

Cite this

Holm, J., Rotenberg, E., & Thorup, M. (2018). Dynamic bridge-finding in õ(log2 n) amortized time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 35-52). Society for Industrial and Applied Mathematics. Proceedings of the Twenty-ninth Annual Acm-siam Symposium
Holm, Jacob ; Rotenberg, Eva ; Thorup, Mikkel. / Dynamic bridge-finding in õ(log2 n) amortized time. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018. pp. 35-52 (Proceedings of the Twenty-ninth Annual Acm-siam Symposium).
@inproceedings{0e48e5ff467141348ac7a1a60581d1e5,
title = "Dynamic bridge-finding in {\~o}(log2 n) amortized time",
abstract = "We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in {\~O}((log n)2) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in O(log n/ log log n) worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to log log n factors.The previous best dynamic bridge finding was an {\~O}((log n)3) amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the O((log n)4) amortized time algorithm by Holm et al.[STOC98, JACM2001].Our approach is based on a different and purely combinatorial improvement of the algorithim of Holm et al., which by itself gives a new combinatorial {\~O}((log n)3) amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed {\~O}((log n)2) amortized time.Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to {\~O}((log n)3).We also offer improvements in space. We describe a general trick which applies to both of our new algorithms, and to the old ones, to get down to linear space, where the previous best use O(m + n log n log log n).Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.",
author = "Jacob Holm and Eva Rotenberg and Mikkel Thorup",
year = "2018",
language = "English",
series = "Proceedings of the Twenty-ninth Annual Acm-siam Symposium",
pages = "35--52",
booktitle = "Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Society for Industrial and Applied Mathematics",

}

Holm, J, Rotenberg, E & Thorup, M 2018, Dynamic bridge-finding in õ(log2 n) amortized time. in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Proceedings of the Twenty-ninth Annual Acm-siam Symposium, pp. 35-52, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans , United States, 07/01/2018.

Dynamic bridge-finding in õ(log2 n) amortized time. / Holm, Jacob; Rotenberg, Eva; Thorup, Mikkel.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018. p. 35-52 (Proceedings of the Twenty-ninth Annual Acm-siam Symposium).

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

TY - GEN

T1 - Dynamic bridge-finding in õ(log2 n) amortized time

AU - Holm, Jacob

AU - Rotenberg, Eva

AU - Thorup, Mikkel

PY - 2018

Y1 - 2018

N2 - We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ((log n)2) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in O(log n/ log log n) worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to log log n factors.The previous best dynamic bridge finding was an Õ((log n)3) amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the O((log n)4) amortized time algorithm by Holm et al.[STOC98, JACM2001].Our approach is based on a different and purely combinatorial improvement of the algorithim of Holm et al., which by itself gives a new combinatorial Õ((log n)3) amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed Õ((log n)2) amortized time.Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to Õ((log n)3).We also offer improvements in space. We describe a general trick which applies to both of our new algorithms, and to the old ones, to get down to linear space, where the previous best use O(m + n log n log log n).Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.

AB - We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ((log n)2) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in O(log n/ log log n) worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to log log n factors.The previous best dynamic bridge finding was an Õ((log n)3) amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the O((log n)4) amortized time algorithm by Holm et al.[STOC98, JACM2001].Our approach is based on a different and purely combinatorial improvement of the algorithim of Holm et al., which by itself gives a new combinatorial Õ((log n)3) amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed Õ((log n)2) amortized time.Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to Õ((log n)3).We also offer improvements in space. We describe a general trick which applies to both of our new algorithms, and to the old ones, to get down to linear space, where the previous best use O(m + n log n log log n).Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.

M3 - Article in proceedings

T3 - Proceedings of the Twenty-ninth Annual Acm-siam Symposium

SP - 35

EP - 52

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Society for Industrial and Applied Mathematics

ER -

Holm J, Rotenberg E, Thorup M. Dynamic bridge-finding in õ(log2 n) amortized time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. 2018. p. 35-52. (Proceedings of the Twenty-ninth Annual Acm-siam Symposium).