Write recursive versions of the Recursive Graph Partitioning algorithm and Recursive spectral 

 

Bisection algorithm. [Hint: Recall that a recursive program unit is a subprogram or function, say foo, which calls itself, so foo is allowed to make a subroutine call to foo within its body. Recursivity is not allowed in FORTRAN but is possible in C or C++.] (a) Give a pseudo-code for the RGB algorithm which processes the subgraphs in any order. (b) Give a pseudo-code for the RGB algorithm case when the larger subgraph is to be processed before the smaller one in any dissection. Is this second version equivalent to Algorithm 13.9?