185 citations · 371 across the 28 of their papers we have counts for
28 papers
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…
Irredundant intervals
Donald E. Knuth
This expository note presents simplifications of a theorem due to Győri and an algorithm due to Franzblau and Kleitman: Given a family of intervals on a linearly ordered se…
On the inversion of in terms of associated Stirling numbers
David J. Jeffrey, Robert M. Corless, David E. G. Hare +1
The function , the solution of for and large enough, has a series expansion in terms of and , with coefficients given in terms of Sti…
Polynomials involving the floor function
Inger Johanne Håland, Donald E. Knuth
Some identities are presented that generalize the formula x^3 = 3x floor(x floor(x)) - 3 floor(x) floor(x floor(x)) + floor(x)^3 + 3 frac(x) frac(x floor(x)) + frac(x)^3 to a repre…
Two-way rounding
Donald E. Knuth
Given real numbers and a permutation~ of , we can always find $\xbar_1,...,\xbar_n\in\{0,1\}$ so that the partial sums $\xbar_1+... +\xbar…
An exact analysis of stable allocation
Donald E. Knuth
Shapley and Scarf introduced a notion of stable allocation between traders and indivisible goods, when each trader has rank-ordered each of the goods. The purpose of this note is t…
Overlapping Pfaffians
Donald E. Knuth
A combinatorial construction proves an identity for the product of the Pfaffian of a skew-symmetric matrix by the Pfaffian of one of its submatrices. Several applications of this i…
Partitioned tensor products and their spectra
Donald E. Knuth
A pleasant family of graphs defined by Godsil and McKay is shown to have easily computed eigenvalues in many cases.
Aztec diamonds, checkerboard graphs, and spanning trees
Donald E. Knuth
This note derives the characteristic polynomial of a graph that represents nonjump moves in a generalized game of checkers. The number of spanning trees is also determined.
Leaper graphs
Donald E. Knuth
An -leaper is a generalized knight that can jump from to or on a rectangular grid. The graph of an -leaper on an $m\ti…
Bracket notation for the `coefficient of' operator
Donald E. Knuth
When is a power series in , many authors now write `' for the coefficient of in , using a notation introduced by Goulden and Jackson in [\GJ, p. 1…
Mini-indexes for literate programs
Donald E. Knuth
This paper describes how to implement a documentation technique that helps readers to understand large programs or collections of programs, by providing local indexes to all identi…
The sandwich theorem
Donald E. Knuth
This report contains expository notes about a function that is popularly known as the Lovász number of a graph~. There are many ways to define , and…
The birth of the giant component
Svante Janson, Donald E. Knuth, Tomasz Łuczak +1
Limiting distributions are derived for the sparse connected components that are present when a random graph on vertices has approximately $\half n$ edges. In particular, we sho…
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…
Theory and practice
Donald E. Knuth
The author argues to Silicon Valley that the most important and powerful part of computer science is work that is simultaneously theoretical and practical. He particularly consider…
Textbook examples of recursion
Donald E. Knuth
We discuss properties of recursive schemas related to McCarthy's ``91 function'' and to Takeuchi's triple recursion. Several theorems are proposed as interesting candidates for mac…
A note on digitized angles
Donald E. Knuth
We study the configurations of pixels that occur when two digitized straight lines meet each other.
Nested satisfiability
Donald E. Knuth
A special case of the satisfiability problem, in which the clauses have a hierarchical structure, is shown to be solvable in linear time, assuming that the clauses have been repres…
Johann Faulhaber and sums of powers
Donald E. Knuth
Early 17th-century mathematical publications of Johann Faulhaber contain some remarkable theorems, such as the fact that the -fold summation of is a polynomial…