We investigate the well-known NP-hard problem of finding an optimal communication subgraph in a given edge-weighted graph. This problem appears in different distributed wireless communication networks, e.g., in wireless sensor networks, when it is necessary to minimize transmission energy consumption. We propose new heuristic algorithms based on variable neighborhood search metaheuristic. Our results have been compared with the best known results, and the numerical experiment showed that, on a large number of instances, our algorithms outperform the previous ones, especially in a case of large dimensions.