This article proposes a new formulation for the maximum leaf spanning tree problem (MLSTP) using network flow concepts to ensure the graph connectivity of the problem’s solutions. Since the MLSTP is NP hard, the MLSTP genetic algorithm (MGA) is also developed to solve large-scale instances. The proposed formulation optimally solved 37 out of 41 instances of existing benchmarks, comparable with results of the available formulations in the literature. MGA solved all of the existing benchmarks in less than 1 min without a significant optimality gap. MGA also found qualified solutions for large-scale instances of up to 2000 vertices in a reasonable time. As a realistic application of MLSTP, a forest fire detection system was developed and successfully simulated for the Iranian Arasbaran forest using a wireless sensor network (WSN). The proposed formulation was used to find the optimal topology of the WSN responsible for the early detection and timely warning of fires in Arasbaran.
