<p>The minimum dominating set (MinDS) problem has gained significant attention in recent years due to its relevance in social and biological networks. This NP-hard problem poses significant computational challenges, especially on ultra-large sparse graphs commonly encountered in real-world applications. Solving such large-scale instances within practical timeframes often necessitates the use of high-performance computing resources. This paper introduces a dual-evaluation mode search algorithm (DemDS) specifically designed for the MinDS problem. For each evaluation mode, DemDS employs a distinct evaluation function for the neighborhood structure. Utilizing the fast incremental evaluation method, the two functions for each mode effectively direct the search process toward various promising areas, with the goal of achieving improved solutions. The proposed DemDS is rigorously tested on three large-scale graph benchmarks. Specifically, the DemDS algorithm achieved the best solution in 80 out of 103 problem instances, updating the upper bounds results in 21 problem instances. Results show that DemDS demonstrates a clear competitive advantage in handling very large graphs, while showing comparable performance with state-of-the art algorithms in smaller instances.</p>