13 citations · 40 across the 21 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
cs.CC2022
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is , obtained…
cs.DS2022
Optimal resizable arrays
Robert E. Tarjan, Uri Zwick
A \emph{resizable array} is an array that can \emph{grow} and \emph{shrink} by the addition or removal of items from its end, or both its ends, while still supporting constant-time…
cs.DS2022
Finding Strong Components Using Depth-First Search
Robert E. Tarjan, Uri Zwick
We survey three algorithms that use depth-first search to find the strong components of a directed graph in linear time: (1) Tarjan's algorithm; (2) a cycle-finding algorithm; and…