Trevor Vaughn

collaborators

4 papers

cs.DS2026

Faster Minimum k-Cut II: Near-Optimal and Deterministic for Weighted Graphs

Trevor Vaughn

The Minimum $k$ -Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least $k$ connected components. We consider only $k \ge…

cs.DS2026

Faster Minimum k-Cut I: Simple and Sparse Weighted Graphs

Jason Li, Trevor Vaughn

The minimum $k$ -cut problem asks for the fewest edges whose removal leaves an input graph with at least $k$ connected components. Previously, the best algorithm for simple graphs r…

cs.DS2026

A Simple Las Vegas Algorithm for Sparse Nonnegative Convolution

Trevor Vaughn

Let $A, B \in Z_{\geq 0}^{n}$ be nonnegative vectors and let $t = ∣ supp (A ⋆ B) ∣$ . We give a Las Vegas algorithm that computes $A ⋆ B$ in $O (t lo g t)$ …

cs.DS2026

Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs

Jason Li, Trevor Vaughn

A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted $n$ -vert…