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
Father Damien

... is the patron of lepers and outcasts, and was recently made the patron of AIDS patients. The world's only Catholic memorial chapel to victims of AIDS, a shrine to ...

 
 
 
This page was created in 34 ms