185 citations · 371 across the 28 of their papers we have counts for
6 papers · 1 filter
Efficient coroutine generation of constrained Gray sequences
Donald E. Knuth, Frank Ruskey
We study an interesting family of cooperating coroutines, which is able to generate all patterns of bits that satisfy certain fairly general ordering constraints, changing only one…
Dancing links
Donald E. Knuth
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes. The fi…
Linear probing and graphs
Donald E. Knuth
Mallows and Riordan showed in 1968 that labeled trees with a small number of inversions are related to labeled graphs that are connected and sparse. Wright enumerated sparse connec…
Shellsort with three increments
Svante Janson, Donald E. Knuth
A perturbation technique can be used to simplify and sharpen A. C. Yao's theorems about the behavior of shellsort with increments . In particular, when and…
The problem of compatible representatives
Donald E. Knuth, Arvind Raghunathan
The purpose of this note is to attach a name to a natural class of combinatorial problems and to point out that this class includes many important special cases. We also show that…
Context-free multilanguages
Donald E. Knuth
This article is a sketch of ideas that were once intended to appear in the author's famous series, "The Art of Computer Programming". He generalizes the notion of a context-free la…