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
List of intelligence agencies

... Intelligence[?] Czechoslovakia Federal Directorate of Intelligence Services[?] (FSZS, Defunct) Hlavni Sprava Rozvedky[?] (HSR, Defunct) Denmark Police Intelligence ...

 
 
 
This page was created in 27.3 ms