Gabow SCC

swMATH ID: 28915
Software Authors: Peter Lammich
Description: Verified Efficient Implementation of Gabow’s Strongly Connected Components Algorithm. 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.
Homepage: https://www.isa-afp.org/entries/Gabow_SCC.html
Dependencies: Isabelle
Related Software: Isabelle/HOL; Isabelle; HOL; Archive Formal Proofs; Edmonds-Karp; Coq; CAVA LTL Modelchecker; Refinement Monadic; Autoref; Dijkstra Shortest Path; Isar; Collections; Separation Logic; z3; GitHub; CakeML; LCF; Locales; CeTA; SPIN
Cited in: 9 Publications

Citations by Year