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|.
Search Encyclopedia
|
Featured Article
|