License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.34
URN: urn:nbn:de:0030-drops-168320
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16832/
Go to the corresponding LIPIcs Volume Portal

Christiansen, Aleksander B. G. ; Holm, Jacob ; Rotenberg, Eva ; Thomassen, Carsten

On Dynamic α + 1 Arboricity Decomposition and Out-Orientation

pdf-format:
LIPIcs-MFCS-2022-34.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{christiansen_et_al:LIPIcs.MFCS.2022.34,
  author =	{Christiansen, Aleksander B. G. and Holm, Jacob and Rotenberg, Eva and Thomassen, Carsten},
  title =	{{On Dynamic \alpha + 1 Arboricity Decomposition and Out-Orientation}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16832},
  URN =		{urn:nbn:de:0030-drops-168320},
  doi =		{10.4230/LIPIcs.MFCS.2022.34},
  annote =	{Keywords: Dynamic graphs, bounded arboricity, data structures}
}

Keywords: Dynamic graphs, bounded arboricity, data structures
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI