Good r-divisions imply optimal amortized decremental biconnectivity
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 846 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 |
Redaktører | Markus Blaser, Benjamin Monmege |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2021 |
Sider | 1-18 |
Artikelnummer | 42 |
ISBN (Elektronisk) | 9783959771801 |
DOI | |
Status | Udgivet - 2021 |
Begivenhed | 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 - Virtual, Saarbrucken, Tyskland Varighed: 16 mar. 2021 → 19 mar. 2021 |
Konference
Konference | 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 |
---|---|
Land | Tyskland |
By | Virtual, Saarbrucken |
Periode | 16/03/2021 → 19/03/2021 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 187 |
ISSN | 1868-8969 |
ID: 298953672