Shucheng Chi

activity

20212024

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2024

Undirected 3-Fault Replacement Path in Nearly Cubic Time

Shucheng Chi, Ran Duan, Benyu Wang +1

Given a graph $G = (V, E)$ and two vertices $s, t \in V$ , the $f$ -fault replacement path ( $f$ FRP) problem computes for every set of edges $F$ where $∣ F ∣ \leq f$ , the distance from $s$ to…

cs.DS2022

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 $n \times n$ matrices is $O ~ (n^{(3 + ω) /2}) = O ~ (n^{2.687})$ , where $ω < 2.373$ is the f…

cs.DS2021

Faster Algorithms for Bounded-Difference Min-Plus Product

Shucheng Chi, Ran Duan, Tianle Xie

Min-plus product of two $n \times n$ 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…