An Important Corollary for the Fast Solution of Dynamic Maximal Clique Enumeration Problems

2014/12/15 by Neal Lawton, Lawton, Neal
Computer Science · #68R10 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #acm:68R10 #cs.DM #msc:68R10

paper · pdf · doi:10.48550/arxiv.1412.4620

5 pages

arxiv created 2014/12/16 · arxiv updated 2014/12/17

Abstract

In this paper we modify an algorithm for updating a maximal clique enumeration after an edge insertion to provide an algorithm that runs in linear time with respect to the number of cliques containing one of the edge's endpoints, whereas existing algorithms take quadratic time.

Related

• Accelerating Maximal Clique Enumeration via Graph Reduction
• Incremental Maintenance of Maximal Cliques in a Dynamic Graph
• A Change-Sensitive Algorithm for Maintaining Maximal Bicliques in a\n Dynamic Bipartite Graph
• An Implicit Enumeration Approach for Maximum Ratio Clique Relaxations
• Poising on Ariadne's thread: An algorithm for computing a maximum clique in polynomial time