Abstract.
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 connected graphs in 1977, and Kreweras related the inversions of trees to the so-called ``parking problem'' in 1980. A combination of these three results leads to a surprisingly simple analysis of the behavior of hashing by linear probing, including higher moments of the cost of successful search.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received November 9, 1997; revised January 15, 1998.
Rights and permissions
About this article
Cite this article
Knuth, D. Linear Probing and Graphs. Algorithmica 22, 561–568 (1998). https://doi.org/10.1007/PL00009240
Issue Date:
DOI: https://doi.org/10.1007/PL00009240