Linear Probing and Graphs
Stanford University (visiting MIT)
refreshments at 3:45pm
2-105 (Note unusual room!)
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.
Speaker's Contact Info: (no email)
Computer Science Department,
Gates Building 4B,
Stanford, CA 94305.
Return to seminar home page
Page loaded on October 01, 1999 at 02:12 PM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.