On Dynamic α+ 1 Arboricity Decomposition and Out-Orientation
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
On Dynamic α+ 1 Arboricity Decomposition and Out-Orientation. / Christiansen, Aleksander B.G.; Holm, Jacob; Rotenberg, Eva; Thomassen, Carsten.
47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. ed. / Stefan Szeider; Robert Ganian; Alexandra Silva. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. p. 1-15 34 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 241).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - On Dynamic α+ 1 Arboricity Decomposition and Out-Orientation
AU - Christiansen, Aleksander B.G.
AU - Holm, Jacob
AU - Rotenberg, Eva
AU - Thomassen, Carsten
N1 - Publisher Copyright: © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - bounded arboricity
KW - data structures
KW - Dynamic graphs
UR - http://www.scopus.com/inward/record.url?scp=85137565588&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2022.34
DO - 10.4230/LIPIcs.MFCS.2022.34
M3 - Article in proceedings
AN - SCOPUS:85137565588
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 15
BT - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
A2 - Szeider, Stefan
A2 - Ganian, Robert
A2 - Silva, Alexandra
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Y2 - 22 August 2022 through 26 August 2022
ER -
ID: 320114252