El problema del árbol dominante mínimo (MDT) consiste en encontrar un subgrafo de peso mínimo a partir de un grafo no dirigido, de modo que cada vértice que no esté en este subgrafo esté conectado a al menos uno de los vértices en él, y el subgrafo esté conectado sin ninguna estructura de anillo. Este artículo presenta un algoritmo de búsqueda de doble vecindario (DNS) para resolver el problema MDT, que integra varias características distintivas, como dos vecindarios que trabajan colaborativamente para optimizar la función objetivo, un método rápido de evaluación de vecindario para aumentar la efectividad de la búsqueda, y varias técnicas de diversificación para ayudar al proceso de búsqueda a salir de la trampa del óptimo local y obtener así mejores soluciones. DNS mejora los mejores resultados conocidos previamente para cuatro instancias de referencia públicas y proporciona resultados competitivos para las restantes. Se investigan varios ingredientes de DNS para demostrar la importancia de las ideas y técnicas propuestas.