86 citations · 243 across the 39 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018★ 4 cited
Distributed Triangle Detection via Expander Decomposition
Yi-Jun Chang, Seth Pettie, Hengjie Zhang
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in…
cs.DS2018
Improved bounds for multipass pairing heaps and path-balanced binary search trees
Dani Dorfman, Haim Kaplan, László Kozma +2
We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient…
cs.DS2018★ 4 cited
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts
Shang-En Huang, Seth Pettie
We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce t…