J O E     S A W A D A
[   Home   ] [   Publications and Research   ] [   Algorithm Code   ]
 
 
  1. Cut-down de Bruijn sequences
        B. Cameron, A. Gündoǧan, and J. Sawada
        Submitted manuscript (May 2022).
  2. Pivot Gray codes for the spanning trees of a graph ft the Fan
        B. Cameron, A. Grubb, and J. Sawada
        Submitted manuscript (Feb 2022).
        Presented at COCOON 2021.
  3. Constructing the first (and coolest) fixed-content universal cycle
        J. Sawada and A. Williams
        Submitted manuscript (Jan 2022).
        Presented at WADS 2021.
  4. Hamiltonicity of k-sided pancake networks with fixed-spin: Efficient generation, ranking, and optimality
        B. Cameron, J. Sawada, W. Therese, and A. Williams
        Algorithmica, to appear (2022).
        Presented at IWOCA 2021.
  5. Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
        E. Sala, J. Sawada, and A. Alhakim
        Submitted manuscript (Apr 2020).
  6. Flip-swap languages in binary reflected Gray code order
        J. Sawada, A. Williams, and D. Wong
        Submitted manuscript (Feb 2022).
        Presented at WORDS 2021.
  7. Investigating the discrepancy property of de Bruijn sequences
        D. Gabric and J. Sawada
        Discrete Mathematics, Vol. 345 (2022) 112780.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. Solving the Sigma-Tau problem
        J. Sawada and A. Williams
        ACM Transactions on Algorithms, Vol. 16 (2019) Article 11 (17 pages).
  15. Ranking and unranking fixed-density necklaces and Lyndon words
        P. Hartman and J. Sawada
        Theoretical Computer Science, Vol 791 (2019) 36-47.
  16. 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.
  17. 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.
  18. Constructing de Bruijn sequences by concatenating smaller universal cycles
        D. Gabric and J. Sawada
        Theoretical Computer Science, Vol. 743 (2018) 12-22.
  19. 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.

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



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

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

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