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

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2018


View graph of relations

We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in <i>Õ</i>((log <i>n</i>)<sup>2</sup>) 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 <i>n</i>/ log log <i>n</i>) worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to log log <i>n</i> factors. The previous best dynamic bridge finding was an <i>Õ</i>((log <i>n</i>)<sup>3</sup>) amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the O((log <i>n</i>)<sup>4</sup>) 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 <i>Õ</i>((log <i>n</i>)<sup>3</sup>) amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed <i>Õ</i>((log <i>n</i>)<sup>2</sup>) amortized time. Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to <i>Õ</i>((log <i>n</i>)<sup>3</sup>). 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(<i>m</i> + <i>n</i> log <i>n</i> log log <i>n</i>). 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
PublisherSIAM - Society for Industrial and Applied Mathematics
Publication date2018
ISBN (electronic)978-1-61197-503-1
StatePublished - 2018
EventTwenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States


ConferenceTwenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans
SeriesProceedings of the Twenty-ninth Annual Acm-siam Symposium
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 142465956