Emergency managers need to assess, combine and process large volumes of information with varying degrees of (un)certainty. To keep track of the uncertainties and to facilitate gaining an understanding of the situation, the information is combined into scenarios: stories about the situation and its development. As the situation evolves, typically more information becomes available and already acknowledged information is changed or revised. Meanwhile, decision-makers need to keep track of the scenarios including an assessment whether the infor-mation constituting the scenario is still valid and relevant for their purposes. Standard techniques to support sce-nario updating usually involve complete scenario re-construction. This is far too time-consuming in emergency management. Our approach uses a graph theoretical scenario formalisation to enable efficient scenario updating. MCDA techniques are employed to decide whether information changes are sufficiently important to warrant scenario updating. A brief analysis of the use-case demonstrates a large gain in efficiency.