4 papers
Undirected 3-Fault Replacement Path in Nearly Cubic Time
Shucheng Chi, Ran Duan, Benyu Wang +1
Given a graph and two vertices , the -fault replacement path (FRP) problem computes for every set of edges where , the distance from to…
Faster Min-Plus Product for Monotone Instances
Shucheng Chi, Ran Duan, Tianle Xie +1
In this paper, we show that the time complexity of monotone min-plus product of two matrices is , where is the f…
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…
Differentiated nonblocking: a new progress condition and a matching queue algorithm
David Y. C. Chan, Shucheng Chi, Vassos Hadzilacos +1
In this paper, we first propose a new liveness requirement for shared objects and data structures, we then give a shared queue algorithm that satisfies this requirement and we prov…