215 citations · 318 across the 83 of their papers we have counts for
3 papers · 1 filter
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and -Time
Danupon Nanongkai, Thatchaphol Saranurak
We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee {\em worst-case update time} a…
Binary search trees and rectangulations
László Kozma, Thatchaphol Saranurak
We revisit the classical problem of searching in a binary search tree (BST) using rotations, and present novel connections of this problem to a number of geometric and combinatoria…
The landscape of bounds for binary search trees
Parinya Chalermsook, Mayank Goswami, László Kozma +2
Binary search trees (BSTs) with rotations can adapt to various kinds of structure in search sequences, achieving amortized access times substantially better than the Theta(log n) w…