## Abstract

We present a deterministic fully-dynamic
data structure for maintaining information about the bridges in a graph.
We support updates in

The previous best dynamic bridge finding was an

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

Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to

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(

Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.

*Õ*((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 language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Society for Industrial and Applied Mathematics |

Publication date | 2018 |

Pages | 35-52 |

ISBN (Electronic) | 978-1-61197-503-1 |

Publication status | Published - 2018 |

Event | 29th Annual ACM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaze, New Orleans French Quarter , New Orleans , United States Duration: 7 Jan 2018 → 10 Jan 2018 Conference number: 29 |

### Conference

Conference | 29th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Number | 29 |

Location | Astor Crowne Plaze, New Orleans French Quarter |

Country | United States |

City | New Orleans |

Period | 07/01/2018 → 10/01/2018 |

Series | Proceedings of the Twenty-ninth Annual Acm-siam Symposium |
---|