Linear probing and graphs

Simple item page
dc.creatorKnuth, Donald E.
dc.date1998-01-15
dc.date.accessioned2026-07-07T03:23:27Z
dc.date.available2026-07-07T03:23:27Z
dc.descriptionMallows 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.
dc.identifierhttps://arxiv.org/abs/cs/9801103
dc.identifierhttp://arxiv.org/abs/cs/9801103
dc.identifierAlgorithmica 22 (1998), no. 4, 561--568
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32949
dc.subjectData Structures and Algorithms
dc.titleLinear probing and graphs
dc.typetext

Files

Collections

arXiv