Maximal strongly connected cliques in directed graphs: algorithms and bounds

DOI10.1016/j.dam.2020.05.027zbMath1472.05061OpenAlexW3035374762MaRDI QIDQ1983136

Kunihiro Wasa, Takeaki Uno, Alessio Conte, Mamadou Moustapha Kanté

Publication date: 15 September 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.05.027

zbMATH Keywords

directed graphsmaximal cliquescommunity detectionbounded delayenumeration algorithmsnetwork analytics

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20)

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Reverse search for enumeration
• Directing Road Networks by Listing Strong Orientations
• Clique Relaxation Models in Social Network Analysis
• Bounded Arboricity to Determine the Local Structure of Sparse Graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• New polynomial delay bounds for maximal subgraph enumeration by proximity search
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Algorithm Theory - SWAT 2004
• The Enumeration of Maximal Cliques of Large Graphs
• Algorithm 457: finding all cliques of an undirected graph
• On cliques in graphs