2026-10-14T14:23:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14593 2024-03-06T09:54:23Z ddc:004 open_access

Incremental Edge Orientation in Forests Bender, Michael A. Kopelowitz, Tsvi Kuszmaul, William Porat, Ely Stein, Clifford edge orientation graph algorithms Cuckoo hashing hash functions For any forest G = (V, E) it is possible to orient the edges E so that no vertex in V has out-degree greater than 1. This paper considers the incremental edge-orientation problem, in which the edges E arrive over time and the algorithm must maintain a low-out-degree edge orientation at all times. We give an algorithm that maintains a maximum out-degree of 3 while flipping at most O(log log n) edge orientations per edge insertion, with high probability in n. The algorithm requires worst-case time O(log n log log n) per insertion, and takes amortized time O(1). The previous state of the art required up to O(log n / log log n) edge flips per insertion. We then apply our edge-orientation results to the problem of dynamic Cuckoo hashing. The problem of designing simple families ℋ of hash functions that are compatible with Cuckoo hashing has received extensive attention. These families ℋ are known to satisfy static guarantees, but do not come typically with dynamic guarantees for the running time of inserts and deletes. We show how to transform static guarantees (for 1-associativity) into near-state-of-the-art dynamic guarantees (for O(1)-associativity) in a black-box fashion. Rather than relying on the family ℋ to supply randomness, as in past work, we instead rely on randomness within our table-maintenance algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael A. Bender and Tsvi Kopelowitz and William Kuszmaul and Ely Porat and Clifford Stein 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.12 urn:nbn:de:0030-drops-145933 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.12 eng https://creativecommons.org/licenses/by/4.0/legalcode