Good r-divisions imply optimal amortized decremental biconnectivity
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Final published version, 846 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 |
Editors | Markus Blaser, Benjamin Monmege |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2021 |
Pages | 1-18 |
Article number | 42 |
ISBN (Electronic) | 9783959771801 |
DOIs | |
Publication status | Published - 2021 |
Event | 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 - Virtual, Saarbrucken, Germany Duration: 16 Mar 2021 → 19 Mar 2021 |
Conference
Conference | 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 |
---|---|
Land | Germany |
By | Virtual, Saarbrucken |
Periode | 16/03/2021 → 19/03/2021 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 187 |
ISSN | 1868-8969 |
- 2-connectivity, Dynamic graphs, Graph minors, Graph separators, R-divisions
Research areas
ID: 298953672