Efficient maximal cliques enumeration in weakly closed graphs
Time: 14:00 -- Location: LRI, 445
summary: We show that the algorithm presented in [J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein. Finding cliques in social networks: A new distribution-free model. SIAM journal on computing, 49(2):448-464, 2020] can be modified to have enumeration time complexity αO(n·poly(c)). Here parameter c is the weakly closure of the graph and α its number of maximal cliques. This result improves on their complexity which was not output sensitive and exponential in the closure of the graph.