Greedy algorithm

Starting with a vertex with the smallest degree, mark its neighbors, and then the neighbors' neighbors. The first $n/p$ marked vertices are taken to form one subdomain and the procedure is applied to the remaining graph until all of the vertices are marked. This algorithm [20] is similar to the RGB algorithm, although it is not a bisection algorithm. Like RGB it has a low complexity of $O(n)$.