A Simple Greedy Algorithm for Dynamic Graph Orientation

Authors Edvin Berglin, Gerth Stølting Brodal



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.12.pdf
  • Filesize: 463 kB
  • 12 pages

Document Identifiers

Author Details

Edvin Berglin
Gerth Stølting Brodal

Cite AsGet BibTex

Edvin Berglin and Gerth Stølting Brodal. A Simple Greedy Algorithm for Dynamic Graph Orientation. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.12

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.
Keywords
  • Dynamic graph algorithms
  • graph arboricity
  • edge orientations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. arXiv preprint arXiv:1506.07076, 2015. Google Scholar
  2. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 692-711. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  3. Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representation of sparse graphs. In Proceedings 6th International Workshop on Algorithms and Data Structures (WADS), volume 1663 of Lecture Notes in Computer Science, pages 342-351. Springer, 1999. Google Scholar
  4. Paul Dietz and Daniel Sleator. Two algorithms for maintaining order in a list. In Proceedings 19th Annual ACM Symposium on Theory of Computing (STOC), pages 365-372. ACM, 1987. Google Scholar
  5. Meng He, Ganggui Tang, and Norbert Zeh. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In Proceedings 25th International Symposium on Algorithms and Computation (ISAAC), volume 8889 of Lecture Notes in Computer Science, pages 128-140. Springer, 2014. Google Scholar
  6. Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596-603, 1992. Google Scholar
  7. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Proceedings 41st International Colloquium Automata, Languages, and Programming (ICALP), Part II, volume 8573 of Lecture Notes in Computer Science, pages 532-543. Springer, 2014. Google Scholar
  8. Łukasz Kowalik. Adjacency queries in dynamic sparse graphs. Information Processing Letters, 102(5):191-195, 2007. Google Scholar
  9. Christos Levcopoulos and Mark H. Overmars. A balanced search tree with O(1) worst-case update time. Acta Informatica, 26(3):269-277, 1988. Google Scholar
  10. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):7, 2016. Google Scholar
  11. David Peleg and Shay Solomon. Dynamic (1+ ε)-approximate matchings: a density-sensitive approach. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 712-729. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  12. Shay Solomon. Fully dynamic maximal matching in constant update time. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 325-334. IEEE, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail