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
Quadratic formula

... that when computing roots numerically, the usual form of the quadratic formula is not ideal. See Loss of significance for details. Derivation The quadratic ...

 
 
 
This page was created in 21.4 ms