2 citations · 4 across the 5 of their papers we have counts for
11 papers · 1 filter
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in- Time Barrier
Anton Bukov, Shay Solomon, Tianyi Zhang
The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U…
Streaming Edge Coloring with Subquadratic Palette Size
Shiri Chechik, Doron Mukhtar, Tianyi Zhang
In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an -node graph arrive in an arbitrary order…
Almost-Optimal Sublinear Additive Spanners
Zihan Tan, Tianyi Zhang
Given an undirected unweighted graph on vertices and edges, a subgraph is a spanner of with stretch function $f: \mathbb{R}_+ \rightarrow \m…
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…
Gomory-Hu Trees in Quadratic Time
Tianyi Zhang
Gomory-Hu tree [Gomory and Hu, 1961] is a succinct representation of pairwise minimum cuts in an undirected graph. When the input graph has general edge weights, classic algorithms…
Faster Cut-Equivalent Trees in Simple Graphs
Tianyi Zhang
Let be an undirected connected simple graph on vertices. A cut-equivalent tree of is an edge-weighted tree on the same vertex set , such that for any pair o…