S. Liu

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2020

Connected Components on a PRAM in Log Diameter Time

S. Cliff Liu, Robert E. Tarjan, Peilin Zhong

We present an $O (lo g d + lo g lo g_{m / n} n)$ -time randomized PRAM algorithm for computing the connected components of an $n$ -vertex, $m$ -edge undirected graph with maximum componen…

cs.DS2018

Simple Concurrent Labeling Algorithms for Connected Components

S. Cliff Liu, Robert E. Tarjan

We study a class of simple algorithms for concurrently computing the connected components of an $n$ -vertex, $m$ -edge graph. Our algorithms are easy to implement in either the COMBI…

cs.DS2018

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

S. Cliff Liu

We present the current fastest deterministic algorithm for $k$ -SAT, improving the upper bound $(2 - 2/ k)^{n + o (n)}$ dues to Moser and Scheder [STOC'11]. The algorithm combines a bra…