Refined pivot selection for maximal clique enumeration in graphs

详细信息    查看全文

• 作者：Kevin A. Naud&eacute ; ^{Kevin.Naude@nmmu.ac.za" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Clique enumeration ; Maximal cliques ; Maximal independent sets
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：1 February 2016
• 年：2016
• 卷：613
• 期：Complete
• 页码：28-37
• 全文大小：595 K

文摘

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.