Refined pivot selection for maximal clique enumeration in graphs
This article re-examines the pivoting BronKerbosch 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 BronKerbosch with Tomita-style pivot selection.
maximal cliques clique enumeration maximal independent sets