This paper introduces the subnet generation problem (SGP) which is a new type of network routing problem that is found, for example, in some peer-to-peer applications. We explore two algorithms to solve the SGP by exploiting its special structure. The first algorithm, the tree search algorithm (TS), is an adaptation of an existing algorithm. TS decomposes the SGP into a master problem solved by a systematic tree search, and a subproblem solved by incom- plete but efficient heuristics. Our question is what happens if we sacrifice the complete search in the master problem in exchange for better exploration of the search space. In order to answer this, we present a second algorithm, the local search algorithm (LS), which replaces the tree search with non-systematic search in the master problem. The two algorithms are compared in an experimental study.