License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.12
URN: urn:nbn:de:0030-drops-82637
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8263/
Go to the corresponding LIPIcs Volume Portal

Berglin, Edvin ; Stølting Brodal, Gerth

A Simple Greedy Algorithm for Dynamic Graph Orientation

pdf-format:
LIPIcs-ISAAC-2017-12.pdf (0.5 MB)

Abstract

Graph orientations with low out-degree are one of several ways to efficiently store sparse graphs. If the graphs allow for insertion and deletion of edges, one may have to flip the orientation of some edges to prevent blowing up the maximum out-degree. We use arboricity as our sparsity measure. With an immensely simple greedy algorithm, we get parametrized trade-off bounds between out-degree and worst case number of flips, which previously only existed for amortized number of flips. We match the previous best worst-case algorithm (in O(log n) flips) for general arboricity and beat it for either constant or super-logarithmic arboricity. We also match a previous best amortized result for at least logarithmic arboricity, and give the first results with worst-case O(1) and O(sqrt(log n)) flips nearly matching degree bounds to their respective amortized solutions.

BibTeX - Entry

@InProceedings{berglin_et_al:LIPIcs:2017:8263,
  author =	{Edvin Berglin and Gerth St\olting Brodal},
  title =	{{A Simple Greedy Algorithm for Dynamic Graph Orientation}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8263},
  URN =		{urn:nbn:de:0030-drops-82637},
  doi =		{10.4230/LIPIcs.ISAAC.2017.12},
  annote =	{Keywords: Dynamic graph algorithms, graph arboricity, edge orientations}
}

Keywords: Dynamic graph algorithms, graph arboricity, edge orientations
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

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