Back to Search
Start Over
Good r-divisions imply optimal amortized decremental biconnectivity
- 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