19 citations · 73 across the 21 of their papers we have counts for
5 papers · 1 filter
Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
Evan Sala, Joe Sawada, Abbas Alhakim
The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert et al.[AIEE Transactions 77 (1958)]. As a greedy algorithm, it has one major downside: it requi…
Investigating the discrepancy property of de Bruijn sequences
Daniel Gabric, Joe Sawada
The discrepancy of a binary string refers to the maximum (absolute) difference between the number of ones and the number of zeroes over all possible substrings of the given binary…
On Prefix Normal Words and Prefix Normal Forms
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták +2
A -prefix normal word is a binary word with the property that no factor has more s than the prefix of the same length; a -prefix normal word is defined analogously. These…
A certifying algorithm for 3-colorability of P5-free graphs
Daniel Bruce, Chinh T. Hoang, Joe Sawada
We provide a certifying algorithm for the problem of deciding whether a P5- free graph is 3-colorable by showing there are exactly six finite graphs that are P5-free and not 3-colo…
k-Colorability of P5-free graphs
C. T. Hoang, J. Sawada, X. Shu
A polynomial time algorithm that determines for a fixed integer k whether or not a P5-free graph can be k-colored is presented in this paper. If such a coloring exists, the algorit…