3 citations · 6 across the 4 of their papers we have counts for
6 papers
Connected Components on a PRAM in Log Diameter Time
S. Cliff Liu, Robert E. Tarjan, Peilin Zhong
We present an -time randomized PRAM algorithm for computing the connected components of an -vertex, -edge undirected graph with maximum componen…
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 -vertex, -edge graph. Our algorithms are easy to implement in either the COMBI…
The Curse and Blessing of Not-All-Equal in k-Satisfiability
S. Cliff Liu
As a natural variant of the -SAT problem, NAE--SAT additionally requires the literals in each clause to take not-all-equal (NAE) truth values. In this paper, we study the wor…
Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
S. Cliff Liu
We present the current fastest deterministic algorithm for -SAT, improving the upper bound dues to Moser and Scheder [STOC'11]. The algorithm combines a bra…
Should Algorithms for Random SAT and Max-SAT be Different?
Sixue Liu, Gerard de Melo
We analyze to what extent the random SAT and Max-SAT problems differ in their properties. Our findings suggest that for random -CNF with ratio in a certain range, Max-SAT can be…
An Efficient Implementation for WalkSAT
Sixue Liu
Stochastic local search (SLS) algorithms have exhibited great effectiveness in finding models of random instances of the Boolean satisfiability problem (SAT). As one of the most wi…