SummaryActive probing is a widely adopted approach for developing effective solutions for network monitoring and diagnosing. However, the use of probing techniques incurs costs in terms of additional network traffic. Furthermore, probing stations are required to be configured and maintained in the network for sending out probes. The set of probes used for fault detection and/or diagnosis (called the target probe set) is selected by a probe selection algorithm from a larger set called the candidate probe set. Most of the existing techniques for selecting the target probe set assume that the candidate probe set will preexist and the set is determined by the configured routing model in the network. In this paper, we address the problem of generating an expanded candidate probe set, which results in the selection of a more efficient target probe set. We propose the use of heuristics and network partitioning strategies for generating the candidate probe set. For evaluating our approach, we perform experiments to generate candidate probe sets for the networks of several types and sizes. The candidate probe sets are used by the existing probe selection algorithms for selecting target probe sets for fault detection and localization. Our results demonstrate that the target probe set selected from the candidate probe set generated using our approach has a reduced cost of monitoring the network.