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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Verified efficient implementation of Gabow’s strongly connected component algorithm. Zbl 1416.68168Lammich, Peter 2014 all top 5 Cited by 10 Authors 7 Lammich, Peter 2 Sefidgar, S. Reza 1 Brunner, Julian 1 Hobor, Aquinas 1 Leow, Wei Xiang 1 Lochbihler, Andreas 1 Mohan, Anshuman 1 Nipkow, Tobias 1 Paulson, Lawrence Charles 1 Wenzel, Makarius Cited in 2 Serials 5 Journal of Automated Reasoning 1 Formal Aspects of Computing Cited in 3 Fields 9 Computer science (68-XX) 3 Combinatorics (05-XX) 2 Operations research, mathematical programming (90-XX) Citations by Year