Christiansen, Aleksander B. G.
[Verfasser:in];
Holm, Jacob
[Verfasser:in];
Rotenberg, Eva
[Verfasser:in];
Thomassen, Carsten
[Verfasser:in]
;
Aleksander B. G. Christiansen and Jacob Holm and Eva Rotenberg and Carsten Thomassen
[Mitwirkende:r]
On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
Titel:
On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
Beteiligte:
Christiansen, Aleksander B. G.
[Verfasser:in];
Holm, Jacob
[Verfasser:in];
Rotenberg, Eva
[Verfasser:in];
Thomassen, Carsten
[Verfasser:in]
Erschienen:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 Õ(n^{3/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 Õ(n^{5/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 Õ(n^{1/2}) time.