Decremental SPQR-trees for planar graphs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- OA-Decremental SPQR-trees for Planar Graphs
Forlagets udgivne version, 508 KB, PDF-dokument
We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over Ω(n) operations, is O(log2 n). Via SPQR-trees, we give a decremental data structure for maintaining 3-vertex connectivity in planar graphs. It answers queries in O(1) time and processes edge deletions and contractions in O(log2 n) amortized time. The previous best supported deletions and insertions in O(√n) time.
Originalsprog | Engelsk |
---|---|
Titel | 26th European Symposium on Algorithms, ESA 2018 |
Redaktører | Hannah Bast, Grzegorz Herman, Yossi Azar |
Antal sider | 16 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 1 aug. 2018 |
Artikelnummer | 46 |
ISBN (Trykt) | 9783959770811 |
DOI | |
Status | Udgivet - 1 aug. 2018 |
Begivenhed | 26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland Varighed: 20 aug. 2018 → 22 aug. 2018 |
Konference
Konference | 26th European Symposium on Algorithms, ESA 2018 |
---|---|
Land | Finland |
By | Helsinki |
Periode | 20/08/2018 → 22/08/2018 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 112 |
ISSN | 1868-8969 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 230343791