Encyclopedia > Expander

  Article Content

Expander

An expander graph is a graph with high vertex or edge expansion.

Let N(S) denote the set of neighbors of S (excluding S itself).

The Vertex Expansion of a graph is the minimum of |N(S)| / |S|.

Let E(A,B) denote the number of edges with one extremity in A and the other in B. Let /S denote the complement of S.

The Edge Expansion of a graph is the minimum E(S,/S) / |S|.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Shinnecock Hills, New York

... family size is 3.00. In the town the population is spread out with 13.8% under the age of 18, 34.0% from 18 to 24, 17.6% from 25 to 44, 20.5% from 45 to 64, and ...

 
 
 
This page was created in 31.4 ms