3 citations · 6 across the 4 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
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 -vertex, -edge graph. Our algorithms are easy to implement in either the COMBI…
cs.CC2018★ 1 cited
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…
cs.DS2018
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…