S. Liu

collaborators

4 papers

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.CC2018

The Curse and Blessing of Not-All-Equal in k-Satisfiability

S. Cliff Liu

As a natural variant of the $k$ -SAT problem, NAE- $k$ -SAT additionally requires the literals in each clause to take not-all-equal (NAE) truth values. In this paper, we study the wor…

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…