Decremental SPQR-trees for planar graphs

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Holm, Jacob
  • Giuseppe F. Italiano
  • Adam Karczmarz
  • Jakub Łacki
  • Eva Rotenberg

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.

OriginalsprogEngelsk
Titel26th European Symposium on Algorithms, ESA 2018
RedaktørerHannah Bast, Grzegorz Herman, Yossi Azar
Antal sider16
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato1 aug. 2018
Artikelnummer46
ISBN (Trykt)9783959770811
DOI
StatusUdgivet - 1 aug. 2018
Begivenhed26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Varighed: 20 aug. 201822 aug. 2018

Konference

Konference26th European Symposium on Algorithms, ESA 2018
LandFinland
ByHelsinki
Periode20/08/201822/08/2018
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind112
ISSN1868-8969

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 230343791