Refined pivot selection for maximal clique enumeration in graphs

This article re-examines the pivoting Bron–Kerbosch algorithm for identifying all maximal cliques within a graph. A curious result is presented: there exist pivot candidates which may be selected with no penalty to the worst-case running time, even if these vertices do not satisfy the established conditions for the known complexity bound. Hence, such pivots may be selected eagerly. A refined pivot selection process is described, and the preservation of the established worst case bound is proved. Additionally, empirical evidence shows that the revised algorithm is notably faster than Bron–Kerbosch with Tomita-style pivot selection.