On Dynamic α+ 1 Arboricity Decomposition and Out-Orientation

Research output: Contribution to journalConference articleResearchpeer-review

2 Downloads (Pure)

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 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.
Original languageEnglish
Article number34
JournalLeibniz International Proceedings in Informatics, LIPIcs
Volume241
Number of pages15
ISSN1868-8969
DOIs
Publication statusPublished - 2022
Event47th International Symposium on Mathematical Foundations of Computer Science - Freihaus building of TU Wien, Vienna, Austria
Duration: 22 Aug 202226 Aug 2022
Conference number: 47
http://www.ac.tuwien.ac.at/mfcs2022/

Conference

Conference47th International Symposium on Mathematical Foundations of Computer Science
Number47
LocationFreihaus building of TU Wien
Country/TerritoryAustria
CityVienna
Period22/08/202226/08/2022
Internet address

Keywords

  • Dynamic graphs
  • Bounded arboricity
  • Data structures

Fingerprint

Dive into the research topics of 'On Dynamic α+ 1 Arboricity Decomposition and Out-Orientation'. Together they form a unique fingerprint.

Cite this