Back to Search Start Over

Good r-divisions imply optimal amortized decremental biconnectivity

Authors :
Blaser, Markus
Monmege, Benjamin
Holm, Jacob
Rotenberg, Eva
Blaser, Markus
Monmege, Benjamin
Holm, Jacob
Rotenberg, Eva
Source :
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 .
Publication Year :
2021

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.

Details

Database :
OAIster
Journal :
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 .
Notes :
application/pdf, English
Publication Type :
Electronic Resource
Accession number :
edsoai.on1322773744
Document Type :
Electronic Resource