Good r-divisions Imply Optimal Amortized Decremental Biconnectivity.

Jacob Holm; Eva Rotenberg

doi:10.1007/S00224-024-10181-Z

Good r-divisions Imply Optimal Amortized Decremental Biconnectivity.

Jacob Holm
, Eva Rotenberg

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

We present a data structure that, given a graph G of n vertices and m edges, and a suitable pair of nested r-divisions of G, preprocesses G in
time and handles any series of edge-deletions in O(m) total time while answering queries to pairwise biconnectivity in worst-case O(1) time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case O(1) time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs.

Original language	English
Journal	Theory Comput. Syst.
Volume	68
Issue number	4
Pages (from-to)	1014-1048
DOIs	https://doi.org/10.1007/S00224-024-10181-Z
Publication status	Published - 27 Jun 2024
Externally published	Yes

Keywords

Dynamic graphs
2-connectivity
Graph minors

Access to Document

10.1007/S00224-024-10181-Z

ERCP: Efficient Recomputation for Changeful Problems
Rotenberg, E. (PI), Berg, S. D. (Collaborator) & Hoog, I. V. D. (Collaborator)
Villum Foundation
01/07/2021 → 30/06/2026
Project: Research

Cite this

@article{854aae6c4e4744c284c3bdd346dc4529,

title = "Good r-divisions Imply Optimal Amortized Decremental Biconnectivity.",

abstract = "We present a data structure that, given a graph G of n vertices and m edges, and a suitable pair of nested r-divisions of G, preprocesses G in time and handles any series of edge-deletions in O(m) total time while answering queries to pairwise biconnectivity in worst-case O(1) time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case O(1) time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs.",

keywords = "Dynamic graphs, 2-connectivity, Graph minors",

author = "Jacob Holm and Eva Rotenberg",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2024",

month = jun,

day = "27",

doi = "10.1007/S00224-024-10181-Z",

language = "English",

volume = "68",

pages = "1014--1048",

journal = "Theory Comput. Syst.",

issn = "1433-0490",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - Good r-divisions Imply Optimal Amortized Decremental Biconnectivity.

AU - Holm, Jacob

AU - Rotenberg, Eva

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2024/6/27

Y1 - 2024/6/27

N2 - We present a data structure that, given a graph G of n vertices and m edges, and a suitable pair of nested r-divisions of G, preprocesses G in time and handles any series of edge-deletions in O(m) total time while answering queries to pairwise biconnectivity in worst-case O(1) time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case O(1) time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs.

AB - We present a data structure that, given a graph G of n vertices and m edges, and a suitable pair of nested r-divisions of G, preprocesses G in time and handles any series of edge-deletions in O(m) total time while answering queries to pairwise biconnectivity in worst-case O(1) time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case O(1) time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs.

KW - Dynamic graphs

KW - 2-connectivity

KW - Graph minors

U2 - 10.1007/S00224-024-10181-Z

DO - 10.1007/S00224-024-10181-Z

M3 - Journal article

SN - 1433-0490

VL - 68

SP - 1014

EP - 1048

JO - Theory Comput. Syst.

JF - Theory Comput. Syst.

IS - 4

ER -

Good r-divisions Imply Optimal Amortized Decremental Biconnectivity.

Abstract

Keywords

Access to Document

Fingerprint

Projects

ERCP: Efficient Recomputation for Changeful Problems

Cite this