Maximal strongly connected cliques in directed graphs: algorithms and bounds

DOI10.1016/J.DAM.2020.05.027MaRDI QIDQ1983136zbMATH OpenOpenAlexFDO

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

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

community detectiondirected graphsbounded delaymaximal cliquesenumeration algorithmsnetwork analytics

Mathematics Subject Classification ID

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

Recommendations

• On maximal cliques with connectivity constraints in directed graphs
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• Listing all maximal cliques in large sparse real-world graphs
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• Parallel maximum clique algorithms with applications to network analysis

Cites work

• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Bounded Arboricity to Determine the Local Structure of Sparse Graphs
• Clique relaxation models in social network analysis
• Directing Road Networks by Listing Strong Orientations
• Efficient enumeration of solutions produced by closure operations
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• Listing all maximal cliques in large sparse real-world graphs
• New polynomial delay bounds for maximal subgraph enumeration by proximity search
• On cliques in graphs
• On maximal cliques with connectivity constraints in directed graphs
• Reverse search for enumeration
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
• The Enumeration of Maximal Cliques of Large Graphs

Cited in

(2)

• On maximal cliques with connectivity constraints in directed graphs
• Toward optimal bounds in the congested clique, graph connectivity and MST

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: Maximal strongly connected cliques in directed graphs: algorithms and bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1983136)