Given a set of network nodes B that are sought to be monitored, and a set of potential monitoring nodes, a subset M of the monitoring nodes is chosen that insures monitoring each node b in B with a pair of nodes m.sub.i and m.sub.j such that no node except b is on both any shortest path from b to m.sub.i and on any shortest path from b to m.sub.j. Some of the nodes in M are chosen in a first step by identifying a subset of B having nodes b that are "t-good" nodes, choosing a subset of potential monitoring nodes as First Partner nodes, and choosing a corresponding subset of potential monitoring nodes as Second Partner nodes. Others are chosen in a second step that handles nodes b that are not "t-good," using a greedy algorithm.