On Dynamic α+ 1 Arboricity Decomposition and Out-Orientation
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 953 KB, PDF-dokument
A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph's edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α + 1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of O(n3/4) when α is at most polylogarithmic in n. Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α + 1, with an update time of O (n5/7), when α is at most polylogarithmic in n. Here, the choice of α + 1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time. However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in O(n1/2) time.
Originalsprog | Engelsk |
---|---|
Titel | 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 |
Redaktører | Stefan Szeider, Robert Ganian, Alexandra Silva |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2022 |
Sider | 1-15 |
Artikelnummer | 34 |
ISBN (Elektronisk) | 9783959772563 |
DOI | |
Status | Udgivet - 2022 |
Begivenhed | 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 - Vienna, Østrig Varighed: 22 aug. 2022 → 26 aug. 2022 |
Konference
Konference | 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 |
---|---|
Land | Østrig |
By | Vienna |
Periode | 22/08/2022 → 26/08/2022 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 241 |
ISSN | 1868-8969 |
Bibliografisk note
Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
ID: 320114252