Standard
Good r-divisions imply optimal amortized decremental biconnectivity. / Holm, Jacob; Rotenberg, Eva.
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. ed. / Markus Blaser; Benjamin Monmege. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. p. 1-18 42 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 187).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Holm, J & Rotenberg, E 2021,
Good r-divisions imply optimal amortized decremental biconnectivity. in M Blaser & B Monmege (eds),
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021., 42, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 187, pp. 1-18, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, Virtual, Saarbrucken, Germany,
16/03/2021.
https://doi.org/10.4230/LIPIcs.STACS.2021.42
APA
Holm, J., & Rotenberg, E. (2021).
Good r-divisions imply optimal amortized decremental biconnectivity. In M. Blaser, & B. Monmege (Eds.),
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 (pp. 1-18). [42] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 187
https://doi.org/10.4230/LIPIcs.STACS.2021.42
Vancouver
Holm J, Rotenberg E.
Good r-divisions imply optimal amortized decremental biconnectivity. In Blaser M, Monmege B, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2021. p. 1-18. 42. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 187).
https://doi.org/10.4230/LIPIcs.STACS.2021.42
Author
Holm, Jacob ; Rotenberg, Eva. / Good r-divisions imply optimal amortized decremental biconnectivity. 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. editor / Markus Blaser ; Benjamin Monmege. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. pp. 1-18 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 187).
Bibtex
@inproceedings{103e97179a11456299ae5a0c6aaca55f,
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 O(m + n) 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 = "2-connectivity, Dynamic graphs, Graph minors, Graph separators, R-divisions",
author = "Jacob Holm and Eva Rotenberg",
year = "2021",
doi = "10.4230/LIPIcs.STACS.2021.42",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "1--18",
editor = "Markus Blaser and Benjamin Monmege",
booktitle = "38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021",
note = "38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 ; Conference date: 16-03-2021 Through 19-03-2021",
}
RIS
TY - GEN
T1 - Good r-divisions imply optimal amortized decremental biconnectivity
AU - Holm, Jacob
AU - Rotenberg, Eva
PY - 2021
Y1 - 2021
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 O(m + n) 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 O(m + n) 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 - 2-connectivity
KW - Dynamic graphs
KW - Graph minors
KW - Graph separators
KW - R-divisions
UR - http://www.scopus.com/inward/record.url?scp=85115247306&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2021.42
DO - 10.4230/LIPIcs.STACS.2021.42
M3 - Article in proceedings
AN - SCOPUS:85115247306
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 18
BT - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
A2 - Blaser, Markus
A2 - Monmege, Benjamin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
Y2 - 16 March 2021 through 19 March 2021
ER -
