El problema del árbol de costo mínimo es un problema bien estudiado. Existen algoritmos de tiempo polinómico para resolverlo. Recientemente, se presentó una nueva variación del problema llamada Problema de Árbol de Costo Mínimo con Restricciones de Precedencia y Tiempos de Espera, y se demostró que es NP-duro. En este trabajo, proponemos nuevos modelos de tamaño polinómico para el problema que son considerablemente más pequeños en comparación con los propuestos anteriormente. Evaluamos y comparamos experimentalmente cada nuevo modelo en términos de tiempo de computación y calidad de las soluciones. Varias mejoras a los límites superiores e inferiores conocidos de los costos de las soluciones óptimas surgen del estudio.