# Verified Efficient Implementation of Gabow's Strongly Connected Components Algorithm

 Title: Verified Efficient Implementation of Gabow's Strongly Connected Components Algorithm Author: Peter Lammich Submission date: 2014-05-28 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. BibTeX: @article{Gabow_SCC-AFP, author = {Peter Lammich}, title = {Verified Efficient Implementation of Gabow's Strongly Connected Components Algorithm}, journal = {Archive of Formal Proofs}, month = may, year = 2014, note = {\url{https://isa-afp.org/entries/Gabow_SCC.html}, Formal proof development}, ISSN = {2150-914x}, } License: BSD License Depends on: CAVA_Automata Used by: Transition_Systems_and_Automata