at most k. Due to the matroid structure of pseudoforests, the pseudoarboricity may be computed in polynomial time. A random bipartite graph with n vertices on each side of its bipartition, and with cn edges chosen independently at random from each of the n2 possible pairs of vertices, is a pseudoforest with high probability whenever c is a constant strictly less than one. This fact plays a key role in the analysis of cuckoo hashing, a data structure for looking up key-value pairs by looking in one of two hash tables at locations determined from the key: one can form a graph, the "cuckoo graph", whose vertices correspond to hash table locations and whose edges link the two locations at which one of the keys might be found, and the cuckoo hashing algorithm succeeds in finding locations for all of its keys if and only if the cuckoo graph is a pseudoforest. Pseudoforests also play a key role in parallel algorithms for graph coloring and related problems. Notes References . . . . . . . . . . . . . . . . . . . . . . . . . External links Matroid theory Graph families Graph theory objects