Verification of the Schorr-Waite Algorithm - From Trees to Graphs

16 pagesInternational audienceThis article proposes a method for proving the correctness of graph algorithms by manipulating their spanning trees enriched with additional references. We illustrate this concept with a proof of the correctness of a (pseudo-)imperative version of the Schorr-Waite algorithm by re finement of a functional one working on trees. It is composed of two orthogonal steps of re finement -- functional to imperative and tree to graph -- fi nally merged to obtain the result. Our imperative speci fications use monadic constructs and syntax sugar, making them close to common imperative languages. This work has been realized within the Isabelle/HOL proof assistant