Massive failures in communication networks are a consequence of natural disasters, heavy blackouts, military and cyber attacks. We tackle the problem of minimizing the time and number of interventions to sufficiently restore the communication network so as to support emergency services after large-scale failures. We propose PRoTOn (Progressive RecOvery and Tomography-based mONitoring), an efficient algorithm for progressive recovery of emergency services. Unlike previous work, assuming centralized routing and complete network observability, PRoTOn addresses the more realistic scenario in which the network relies on the existing routing protocols, and knowledge of the network state is partial and uncertain. Simulation results carried out on real topologies show that our algorithm outperforms previous solutions in terms of cumulative routed flow, repair costs and recovery time in both static and dynamic failure scenarios.