Jump to content

Disperser

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Conversion script (talk | contribs) at 15:43, 25 February 2002 (Automated conversion). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

An (N,M,D,K,e)-disperser is a bipartite graph with N nodes on the left side, each with degree D, and M nodes on the right side, such that every subset of K nodes on the left side is connected to more than (1-e) fraction of the nodes on the right (i.e. more than (1-e)M nodes).

Retrieved from "https://en.wikipedia.org/w/index.php?title=Disperser&oldid=83684"