24 citations · 151 across the 43 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Short Cycles via Low-Diameter Decompositions
Yang P. Liu, Sushant Sachdeva, Zejun Yu
We present improved algorithms for short cycle decomposition of a graph. Short cycle decompositions were introduced in the recent work of Chu et al, and were used to make progress…
cs.DS2018
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, Richard Peng +3
We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…
cs.CC2018★ 1 cited
Near-optimal approximation algorithm for simultaneous Max-Cut
Amey Bhangale, Subhash Khot, Swastik Kopparty +2
In the simultaneous Max-Cut problem, we are given weighted graphs on the same set of vertices, and the goal is to find a cut of the vertex set so that the minimum, over the…