15 citations · 41 across the 17 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021
Maintaining Exact Distances under Multiple Edge Failures
Ran Duan, Hanlin Ren
We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph and an arbitrarily larg…
cs.DS2021
Faster Algorithms for Bounded-Difference Min-Plus Product
Shucheng Chi, Ran Duan, Tianle Xie
Min-plus product of two matrices is a fundamental problem in algorithm research. It is known to be equivalent to APSP, and in general it has no truly subcubic algorithm…
cs.DS2021
Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
Yi-Jun Chang, Ran Duan, Shunhua Jiang
We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device has a unique identifier in . Energy i…