Maximal strongly connected cliques in directed graphs: algorithms and bounds

DOI10.1016/J.DAM.2020.05.027zbMATH Open1472.05061OpenAlexW3035374762MaRDI QIDQ1983136FDOQ1983136

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

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)

Cites Work

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

Cited In (1)

• Toward optimal bounds in the congested clique, graph connectivity and MST

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)