Efficient maximal cliques enumeration in weakly closed graphs

2023/03/04 by George Manoussakis, Manoussakis, George · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2303.02390

openalex publication_date 2023/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 (npoly(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.

Cited by

• Social Networks: Enumerating Maximal Community Patterns in c-Closed Graphs

Related

• Finding Cliques in Social Networks: A New Distribution-Free Model
• Social Networks: Enumerating Maximal Community Patterns in c-Closed Graphs
• FPT Algorithms for Finding Near-Cliques in c-Closed Graphs
• Engineering Algorithms for ℓ-Isolated Maximal Clique Enumeration
• Finding Maximum Cliques in Large Networks