Verified Efficient Implementation of Gabow's Strongly Connected Components Algorithm

Peter Lammich 🌐

May 28, 2014

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

We present an Isabelle/HOL formalization of Gabow's algorithm for finding the strongly connected components of a directed graph. Using data refinement techniques, we extract efficient code that performs comparable to a reference implementation in Java. Our style of formalization allows for re-using large parts of the proofs when defining variants of the algorithm. We demonstrate this by verifying an algorithm for the emptiness check of generalized Büchi automata, re-using most of the existing proofs.

License

BSD License

Topics

Session Gabow_SCC