Combinatorial families that are exponentially far from being listable in Gray code sequence

DOI10.1090/S0002-9947-99-02229-1zbMath0918.05107MaRDI QIDQ4216327

Ted Chinburg, Carla D. Savage, Herbert S. Wilf

Publication date: 26 October 1998

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

nonexistence; NP-complete; existence problem; Gray code; Hamiltonian path problem

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

05A05: Permutations, words, matrices

68R10: Graph theory (including graph drawing) in computer science

05E99: Algebraic combinatorics

11C08: Polynomials in number theory

11L03: Trigonometric and exponential sums (general theory)

94B25: Combinatorial codes

05C45: Eulerian and Hamiltonian graphs

Cites Work

• Unnamed Item
• String overlaps, pattern matching, and nontransitive games
• Gray codes for \(A\)-free strings
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Updating the hamiltonian problem—A survey
• A Survey of Combinatorial Gray Codes