J O E     S A W A D A [   Home   ] [   Publications and Research   ] [   Algorithm Code   ]

` Random generation of universal cycles and de Bruijn sequences     J. Sawada and D. Gabric     Submitted manuscript (2025) Maximize the rightmost digit: Gray codes for restricted growth strings     Y. Qiu, J. Sawada, and A. Williams     Presented at WALCOM 2025 Constructing k-ary orientable sequences with asymptotically optimal length     D. Gabric and J. Sawada     Design, Codes and Cryptography (2025) Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions     J. Sawada, J. Sears, A. Trautim, and A. Williams     Submitted manuscript (2024) Construction of orientable sequences in O(1)-amortized time per bit     D. Gabric and J. Sawada     Submitted manuscript (2024)     Presented at CPM 2024 Cut-down de Bruijn sequences     B. Cameron, A. Gündoǧan, and J. Sawada     Discrete Mathematics, Vol. 345 No. 1 (2025) Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences     E. Sala, J. Sawada, and A. Alhakim     ACM Transactions on Algorithms, Vol. 21 (2024) 1-33 Pivot Gray codes for the spanning trees of a graph ft the Fan     B. Cameron, A. Grubb, and J. Sawada     Graphs and Combinatorics, Vol. 40 (2024)     Presented at COCOON 2021 Vertex-critical (P3 + l P1)-free and vertex-critical (gem, co-gem)-free graphs     T. Abuadas, B. Cameron, C. Hoàng, and J. Sawada     Discrete Applied Mathematics, Vol. 344 No. 4 (2024) 179-187     Presented at Coast Combinatorics Conference 2023 Constructing the first (and coolest) fixed-content universal cycle     J. Sawada and A. Williams     Algorithmica, Vol. 85 (2023) 1754-1785     Presented at WADS 2021 Hamiltonicity of k-sided pancake networks with fixed-spin: Efficient generation, ranking, and optimality     B. Cameron, J. Sawada, W. Therese, and A. Williams     Algorithmica, Vol. 85 (2023) 717-744     Presented at IWOCA 2021 Flip-swap languages in binary reflected Gray code order     J. Sawada, A. Williams, and D. Wong     Theoretical Computer Science, Vol. 933 (2022) 138-148     Presented at WORDS 2021 Investigating the discrepancy property of de Bruijn sequences     D. Gabric and J. Sawada     Discrete Mathematics, Vol. 345 (2022) Dichotomizing k-vertex-critical H-free graphs for H of order four     B. Cameron, C. Hoàng, J. Sawada     Discrete Applied Mathematics, Vol. 312 (2022) 106-115 Gray codes and symmetric chains     P. Gregor, S. Jäger, T. Mütze, J. Sawada, and K. Wille     Journal of Combinatorial Theory Series B, Vol. 153 (2022) 31-60     Presented at ICALP 2018 Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions     A. Alhakim, E. Sala, and J. Sawada     Theoretical Computer Science, Vol. 852 (2021) 73-77 Generating a Gray code for prefix normal words in amortized polylogarithmic time per word     P. Burcsi, G. Fici, Z. Lipták, R. Raman, and J. Sawada     Theoretcial Computer Science, Vol. 842 (2020) 86-99 Efficient universal cycle constructions for weak orders     J. Sawada and D. Wong     Discrete Mathemetics, Vol. 343 (2020) Article 112022     Presented at the 30th Coast Combinatorics Conference A successor rule framework for constructing k-ary de Bruijn sequences and universal cycles     D. Gabric, J. Sawada, A. Williams, and D. Wong     IEEE Transactions on Information Theory, Vol. 66 (2020) 679-687     ERRATUM: In Example 2, α8 should be attached to α4 based on the applied successor rule. Solving the Sigma-Tau problem     J. Sawada and A. Williams     ACM Transactions on Algorithms, Vol. 16 (2019) Article 11 (17 pages) Ranking and unranking fixed-density necklaces and Lyndon words     P. Hartman and J. Sawada     Theoretical Computer Science, Vol 791 (2019) 36-47 A Pascal-like bound for the number of necklaces with fixed density     I. Heckenberger and J. Sawada     Theoretical Computer Science, Vol. 778 (2019) 73-77 A framework for constructing de Bruijn sequences via simple successor rules     D. Gabric, J. Sawada, A. Williams, and D. Wong     Discrete Mathemetics, Vol. 341 No. 11 (2018) 2977-2987 Constructing de Bruijn sequences by concatenating smaller universal cycles     D. Gabric and J. Sawada     Theoretical Computer Science, Vol. 743 (2018) 12-22 A Hamilton path for the Sigma-Tau problem     J. Sawada and A. Williams     SIAM-ACM Symposium on Discrete Algorithms (2018) 568-575     Presented at SODA 2018 Constructing de Bruijn sequences with co-lexicographic order: The k-ary grandmama sequence     P. Dragon, O. Hernandez, J. Sawada, A. Williams, and D. Wong     European Journal of Combinatorics, Vol. 72 (2018) 1-11 Necklaces and Lyndon words in colexicographic and binary reflected Gray code order     J. Sawada, A. Williams, and D. Wong     Journal of Discrete Algorithms, Vol. 46-47 (2017) 25-35 A de Bruijn sequence construction by concatenating cycles of the complemented cycling register     D. Gabric and J. Sawada     11th Internatinal Conference on WORDS, LNCS 10432 (2017) 49-58     Presented at WORDS 2017 Finding the largest fixed-density necklace and Lyndon word     P. Hartman and J. Sawada     Information Processing Letters, Vol. 125 (2017) 15-19 A practical algorithm to rank necklaces, Lyndon words, and de Bruijn sequences     J. Sawada and A. Williams     Journal of Discrete Algorithms, Vol. 43 (2017) 95-110 A simple shift rule for k-ary de Bruijn sequences     J. Sawada, A. Williams, and D. Wong     Discrete Mathematics, Vol. 340 No. 3 (2017) 524-531 On prefix normal words and prefix normal forms     P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, J. Sawada     Theoretical Computer Science, Vol. 659 (2017) 1-13     Presented at CPM 2014 and FUN 2014 Efficient Algorithms for Ranking, Unranking, and Generating Stacks of Pancakes and Burnt Pancakes     J. Sawada and A. Williams     Unsubmitted manuscript (2016) Greedy flipping of pancakes and burnt pancakes     J. Sawada and A. Williams     Discrete Applied Mathematics, Vol. 210 (2016) 61-74     Presented at LAGOS 2013 Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles     J. Sawada, A. Williams, and D. Wong     Electronic Journal of Combinatorics, Vol. 23 No. 1 (2016) #P1.24 Successor rules for flipping pancakes and burnt pancakes     J. Sawada and A. Williams     Theoretical Computer Science, Vol. 609, No. 1 (2016) 60-75     Presented at FUN 2014. A surprisingly simple de Bruijn sequence construction     J. Sawada, A. Williams, and D. Wong     Discrete Mathematics, Vol. 339 No. 1 (2016) 127-131 Charm bracelets and their application to the construction of periodic Golay pairs     D. Dokovic, I Kotsireas, D. Recoskie, J. Sawada     Discrete Applied Mathematics, Vol. 188, Issue C (2015) 32-40 Constructions of k-critical P5-free graphs     C. Hoàng, B. Moore, D. Recoskie, J. Sawada, and M. Vatshelle     Discrete Applied Mathematics, Vol. 182 (2015) 91-98 The eight 5-critical {P5,C5}-free graphs. Snakes, coils, and single-track circuit codes with spread k     S. Hood, D. Recoskie, J. Sawada and C. Wong     Journal of Combinatorial Optimization, Vol. 30, No. 1 (2015) 42-62 Normal, abby normal, prefix normal     P. Burcsi, G. Fici, Z. Liptak, F. Ruskey, J. Sawada     Seventh International Conference on Fun with Algorithms (FUN 2014), Italy     Presented at FUN 2014 On combinatorial generation of prefix normal words     P. Burcsi, G. Fici, Z. Liptak, F. Ruskey, J. Sawada     25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), Russia     Presented at CPM 2014 The lexicographically smallest universal cycle for binary strings with minimum specified weight     J. Sawada, A. Williams, and D. Wong     Journal of Discrete Algorithms, 28 (2014) 31-40 The harassed waitress problem     J. Sawada (Harrah Essed) and A. Williams (Wei Therese)     Seventh International Conference on Fun with Algorithms (FUN 2014), Italy     Presented at FUN 2014 Universal cycles for weight-range binary strings     J. Sawada, A. Williams, and D. Wong     International Workshop on Combinatorial Algorithms (IWOCA, 2013), France     Presented at IWOCA 2013 A Gray code for fixed-density necklaces and Lyndon words in constant amortized time     J. Sawada and A. Williams     Theoretical Computer Science, Vol. 502, No. 2 (2013) 46-54 Generating bracelets with fixed content     S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine     Theoretical Computer Science, Vol. 475 (2013) 103-112 Finding and listing induced paths     C. Hoàng, M. Kaminski, J. Sawada and R. Sritharan     Discrete Applied Mathematics, 161 (2013) 633-641 De Bruijn sequences for fixed-weight binary strings     F. Ruskey, J. Sawada and A. Williams     SIAM Journal on Discrete Mathematics, Vol. 26, No. 2 (2012) 605-617 Efficient oracles for binary bubble languages     J. Sawada and A. Williams     Electronic Journal of Combinatorics, Vol. 19, No. 1 (2012) #P42 (20 pages) Binary bubble languages and cool-lex order     F. Ruskey, J. Sawada and A. Williams     Journal of Combinatorial Theory, Series A 119 (2012) 155-169 Stamp foldings, semi-meanders, and open meanders: fast generation algorithms     J. Sawada and R. Li     Electronic Journal of Combinatorics, Vol. 19, No. 2 (2012) P#43 (16 pages) De Bruijn sequences for the binary strings with maximum density     J. Sawada, B. Stevens, and A. Williams     5th International Workshop on Algorithms and Computation (WALCOM) 2011, India, LNCS 6552 (2011) 182-190     Presented at WALCOM 2011 A fast algorithm to generate open meandric systems and meanders     B. Bobier and J. Sawada     Transactions on Algorithms, Vol. 6, No. 2 (2010) 12 pages Deciding k-colorability of P5-free graphs in polynomial time     C. Hoàng, M. Kaminski, V. Lozin, J. Sawada, and X. Shu     Algorithmica, Vol. 57, No 1 (2010) 74-81 Gray codes for reflectable languages     R. Li and J. Sawada     Information Processing Letters, Vol. 209, No. 5 (2009) 296-300 A certifying algorithm for 3-colorability of P5-free graphs     D. Bruce, C. Hoàng, and J. Sawada     The 20th International Symposium on Algorithms and Computation (ISAAC 2009), LNCS 5878 (2009) 594-604     Presented at ISAAC 2009 The 6 minimal graphs that are both P5-free and not 3-colorable. Magic labelings on cycles and wheels     A. Baker and J. Sawada     The 2nd Annual International Conference on Combinatorial Optimization and Applications, (COCOA '08) LNCS 5165 (2008) 361-373     Presented at COCOA 2008 A note on k-colorability of P5-free graphs     C. Hoàng, M. Kaminski, V. Lozin, J. Sawada, and X. Shu     33rd International Symposium on Mathematical Foundations of Computer Scienc (MFCS'08), LNCS 5162 (2008) 387-394     Presented at MFCS 2008 A simple Gray code to list all minimal signed binary representations     J. Sawada     SIAM Journal on Discrete Mathematics, Vol. 21, No. 1 (2007) 16-25     Presented at GRACO 2005 A fast algorithm to generate Beckett-Gray codes     J. Sawada and D. Wong     Electronic Notes in Discrete Mathematics (EuroComb 2007) 29 (2007) 571-577     Presented at EUROCOMB 2007 Generating rooted and free plane trees     J. Sawada     ACM Transactions on Algorithms, Vol. 2, No. 1 (2006) 1-13 A loopless Gray code for minimal signed-binary representations     G. Manku, J. Sawada     13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005) 438-447     Presented at ESA 2005 Oracles for vertex elimination orderings     J. Sawada     Theoretical Computer Science, Vol. 341, No. 1-3 (2005) 73-90 From a simple elimination ordering to a strong elimination ordering in linear time     J. Sawada, J.P. Spinrad     Information Processing Letters, Vol. 86, No. 6 (2003) 299-302 Generating and characterizing the perfect elimination orderings of a chordal graph     L.S. Chandran, L. Ibarra, F. Ruskey, J. Sawada     Theoretical Computer Science, Vol. 307, No.2 (2003) 303-317 Bent Hamilton cycles in d-dimensional grid graphs     F. Ruskey, J. Sawada     The Electronic Journal of Combinatorics, Vol. 10 No. 1 (2003) R1     Presented at SEICCGTC 2002 A fast algorithm to generate necklaces with fixed content     J. Sawada     Theoretical Computer Science, Vol. 301, No.1-3 (2003) 477-489 Generating Lyndon brackets     J. Sawada and F. Ruskey     Journal of Algorithms, Vol. 46, No. 1 (2003) 21-26 Euclidean strings     J. Ellis, F. Ruskey, J. Sawada, J. Simpson     Theoretical Computer Science, Vol. 301, No. 1-3 (2003) 321-340     Presented at AWOCA 2000 The number of irreducible polynomials over GF(2) with given trace and subtrace     K. Cattell, C.R. Miers, F. Ruskey, J. Sawada, M. Serra     Jounal of Combinatorial Mathematics and Combinatorial Computing, 47 (2003) 31-64 A fast algorithm for generating non-isomorphic chord diagrams     J. Sawada     SIAM Journal on Discrete Mathematics, Vol. 15, No. 4 (2002) 546-561 Generating bracelets in constant amortized time     J. Sawada     SIAM Journal on Computing, Vol. 31, No. 1 (2001) 259-268     ERRATUM: The third to last line of the code in Figure 3.1 should read:     if t=1 then GenBracelets(t+1,t,1,1,1,RS); The number of irreducible polynomials and Lyndon words with given trace     F. Ruskey, C.R. Miers, and J. Sawada     SIAM J. Discrete Math., Vol. 14, No 2. (2001) 240-245 Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2)     K. Cattell, F. Ruskey, J. Sawada, M. Serra and C.R. Miers     Journal of Algorithms, Vol. 37, No. 2 (2000) 267-282     Presented at SODA 2000 Generating necklaces and strings with forbidden substrings     F. Ruskey and J. Sawada     6th Annual International Combinatorics and Computing Conference (COCOON), LNCS 1858 (2000) 330-339     Presented at COCOON 2000 An efficient algorithm for generating necklaces with fixed density     F. Ruskey and J. Sawada     SIAM Journal on Computing, 29 (1999) 671-684     Presented at SODA 1999