Abstract: Cooperative relay scheme has been proposed to deal with the heterogeneity of spectrum availability and traffic demand of secondary users in cognitive radio networks. According to this scheme, relay node can bridge the source and the destination using its common channels between those two nodes, as a result, spectrum resource can be better matched to traffic demand of secondary users and efficient spectrum allocation can be achieved. Two algorithms—parallel algorithm and greedy algorithm—are proposed based on maximum flow theory to solve the problem of relay selection and channel allocation in cognitive radio networks, in which the scheme of cooperative relay is used and common available channels probably exist. The complexity of both algorithms is analyzed. Simulation results show that both algorithms are able to allocate the resources more effectively, so as to improve the spectrum efficiency and the throughput of the network. Parallel algorithm can achieve the optimal solution, but its complexity grows rapidly with the channels’ common available degree. Limited by the parallel processing ability, it can only be applied when this degree is not high. Otherwise if the parallel processing ability is exceeded, the greedy algorithm should be selected, which may not necessarily be the optimal solution, but has low complexity and is closer to the optimum solution when there are more common channels.