185 citations · 371 across the 28 of their papers we have counts for
8 papers · 1 filter
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…