Listing Maximal Subgraphs Satisfying Strongly Accessible Properties

DOI10.1137/17M1152206zbMath1409.05108arXiv1803.03659OpenAlexW2926809310WikidataQ128093206 ScholiaQ128093206MaRDI QIDQ4631095

Alessio Conte, Andrea Marino, Luca Versari, Roberto Grossi

Publication date: 24 April 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.03659

zbMATH Keywords

polynomial delayenumeration algorithmsspace efficiencynetwork miningnetwork analyticsgraphs and set systemsMCCIS

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Enumeration of support-closed subsets in confluent systems ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Polynomial-delay enumeration algorithms in set systems ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ Maximal strongly connected cliques in directed graphs: algorithms and bounds ⋮ Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

Uses Software

• Algorithm 457
• ChemmineR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Listing closed sets of strongly accessible set systems with applications to data mining
• An efficient algorithm for solving pseudo clique enumeration problem
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Enumeration aspects of maximal cliques and bicliques
• On generating all maximal independent sets
• On enumerating all minimal solutions of feedback problems
• Efficient enumeration of all minimal separators in a graph
• Enumerating all connected maximal common subgraphs in two graphs
• Finding maximal common subgraphs via time-space efficient reverse search
• A paradigm for listing \((s,t)\)-cuts in graphs
• Reverse search for enumeration
• A note on the derivation of maximal common subgraphs of two directed or undirected graphs
• Arboricity and Subgraph Listing Algorithms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Algorithm Theory - SWAT 2004
• Database Theory - ICDT 2005
• Graph isomorphism in quasipolynomial time [extended abstract]
• The Enumeration of Maximal Cliques of Large Graphs
• Algorithm 457: finding all cliques of an undirected graph
• Computing and Combinatorics

This page was built for publication: Listing Maximal Subgraphs Satisfying Strongly Accessible Properties