Dennis Wong | SUNYK


Universal cycles and de Bruijn sequences

universal cycle for a set S is a cyclic sequence u1u2 … u|S| where each substring of length n corresponds to a unique object in S. As an example, the cyclic sequence in the figure is a universal cycle (de Bruijn sequence) for the set of length 6 binary strings, where the 64 unique length 6 binary strings appear exactly once as a substring when the sequence is considered cyclicly.

Our goal is to study the existence of universal cycle for combinatorial objects, and efficiently construct one if such cycle exists.

Gray codes

Gray code for a set S is a listing s1, s2 ,…, s|S| of the elements of S such that consecutive strings in the listing differ by a small amount of changes. As an example, the listing in the figure is a Gray code for the set of length 4 binary strings where consecutive strings differ by exactly one bit. A universal cycle can also be considered as a Gray code, where consecutive strings differ by a single shift and also at most one bit change.

Our goal is to study the existence of Gray codes and devise efficient algorithms to generate Gray codes for various combinatorial objects.

Negative cycle detection

We study the problem of finding a negative weighted cycle in a directed weighted graph. As an example, the directed weighted graph on the right has a negative cycle (a) -> (b) -> (c) with weight equal to 5+(-20)+10 = -5.

Our research studies the properties of negative cycles in directed weighted graphs and improves the runtime of a wide range of commonly used algorithms in this area.