Incremental Edge Orientation in Forests

DOI10.4230/LIPICS.ESA.2021.12MaRDI QIDQ6075896zbMATH OpenOpenAlexFDO

Authors Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat, Clifford Stein

Publication date 20 September 2023

Full work available at URL https://arxiv.org/abs/2107.02318

zbMATH Keywords

Cuckoo hashingedge orientationgraph algorithmshash functions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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(loglogn)$ edge orientations per edge insertion, with high probability in $n$. The algorithm requires worst-case time $O(lognloglogn)$ per insertion, and takes amortized time $O(1)$. The previous state of the art required up to $O(logn/loglogn)$ edge flips per insertion. We then apply our edge-orientation results to the problem of dynamic Cuckoo hashing. The problem of designing simple families $mathcalH$ of hash functions that are compatible with Cuckoo hashing has received extensive attention. These families $mathcalH$ are known to satisfy emph{static guarantees}, but do not come typically with emph{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 $mathcalH$ to supply randomness, as in past work, we instead rely on randomness within our table-maintenance algorithm.

Cited in

(4)

• Forest Alignment with Affine Gaps and Anchors
• The bi-dimensional directed IDLA forest
• Improved dynamic colouring of sparse graphs
• Insertion time of random walk cuckoo hashing below the peeling threshold

This page was built for publication: Incremental Edge Orientation in Forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075896)