J O E     S A W A D A
[   Home   ] [   Publications and Research   ] [   Algorithm Code   ]
 
 
  1. Construction of orientable sequences in O(1)-amortized time per bit
        D. Gabric and J. Sawada
        Submitted manuscript
        Presented at CPM 2024

  2. Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions
        J. Sawada, J. Sears, A. Trautim, and A. Williams
        Submitted manuscript
  3. Cut-down de Bruijn sequences
        B. Cameron, A. Gündoǧan, and J. Sawada
        Discrete Mathematics - revision pending (2024)
  4. Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
        E. Sala, J. Sawada, and A. Alhakim
        ACM Transactions on Algorithms - revision pending (2024)
  5. Pivot Gray codes for the spanning trees of a graph ft the Fan
        B. Cameron, A. Grubb, and J. Sawada
        Graphs and Combinatorics, to appear (2024)
        Presented at COCOON 2021

  6. 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

  7. Constructing the first (and coolest) fixed-content universal cycle
        J. Sawada and A. Williams
        Algorithmica, Vol. 85 (2023) 1754-1785
        Presented at WADS 2021

  8. 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
  9. 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
  10. Investigating the discrepancy property of de Bruijn sequences
        D. Gabric and J. Sawada
        Discrete Mathematics, Vol. 345 (2022) 112780
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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.
  17. Solving the Sigma-Tau problem
        J. Sawada and A. Williams
        ACM Transactions on Algorithms, Vol. 16 (2019) Article 11 (17 pages)
  18. Ranking and unranking fixed-density necklaces and Lyndon words
        P. Hartman and J. Sawada
        Theoretical Computer Science, Vol 791 (2019) 36-47
  19. 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
  20. 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
  21. Constructing de Bruijn sequences by concatenating smaller universal cycles
        D. Gabric and J. Sawada
        Theoretical Computer Science, Vol. 743 (2018) 12-22
  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


  23. 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
  24. 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
  25. 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
  26. Finding the largest fixed-density necklace and Lyndon word
        P. Hartman and J. Sawada
        Information Processing Letters, Vol. 125 (2017) 15-19
  27. 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
  28. 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
  29. 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
  30. Efficient Algorithms for Ranking, Unranking, and Generating Stacks of Pancakes and Burnt Pancakes
        J. Sawada and A. Williams
        Unsubmitted manuscript (2016)
  31. Greedy flipping of pancakes and burnt pancakes
        J. Sawada and A. Williams
        Discrete Applied Mathematics, Vol. 210 (2016) 61-74
        Presented at LAGOS 2013
  32. 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




  33. 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.
  34. A surprisingly simple de Bruijn sequence construction
        J. Sawada, A. Williams, and D. Wong
        Discrete Mathematics, Vol. 339 No. 1 (2016) 127-131
  35. 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
  36. 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.

  37. 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
  38. 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
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. Generating bracelets with fixed content
        S. Karim, J. Sawada, Z. Alamgirz, and S. M. Husnine
        Theoretical Computer Science, Vol. 475 (2013) 103-112
  45. Finding and listing induced paths
        C. Hoàng, M. Kaminski, J. Sawada and R. Sritharan
        Discrete Applied Mathematics, 161 (2013) 633-641
  46. 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
  47. Efficient oracles for binary bubble languages
        J. Sawada and A. Williams
        Electronic Journal of Combinatorics, Vol. 19, No. 1 (2012) #P42 (20 pages)
  48. Binary bubble languages and cool-lex order
        F. Ruskey, J. Sawada and A. Williams
        Journal of Combinatorial Theory, Series A 119 (2012) 155-169
  49. 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)
  50. 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
  51. 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
  52. 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
  53. Gray codes for reflectable languages
        R. Li and J. Sawada
        Information Processing Letters, Vol. 209, No. 5 (2009) 296-300
  54. 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.

  55. 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
  56. 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
  57. 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
  58. 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
  59. Generating rooted and free plane trees
        J. Sawada
        ACM Transactions on Algorithms, Vol. 2, No. 1 (2006) 1-13
  60. 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
  61. Oracles for vertex elimination orderings
        J. Sawada
        Theoretical Computer Science, Vol. 341, No. 1-3 (2005) 73-90
  62. 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
  63. 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
  64. 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
  65. A fast algorithm to generate necklaces with fixed content
        J. Sawada
        Theoretical Computer Science, Vol. 301, No.1-3 (2003) 477-489
  66. Generating Lyndon brackets
        J. Sawada and F. Ruskey
        Journal of Algorithms, Vol. 46, No. 1 (2003) 21-26
  67. 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
  68. 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
  69. A fast algorithm for generating non-isomorphic chord diagrams
        J. Sawada
        SIAM Journal on Discrete Mathematics, Vol. 15, No. 4 (2002) 546-561
  70. 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);

  71. 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
  72. 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
  73. 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
  74. 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