Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
From MaRDI portal
(Redirected from Publication:4631095)
Abstract: Algorithms for listing the subgraphs satisfying a given property (e.g.,being a clique, a cut, a cycle, etc.) fall within the general framework of set systems. A set system (U, F) uses a ground set U (e.g., the network nodes) and an indicator F, subset of 2^U, of which subsets of U have the required property. For the problem of listing all sets in F maximal under inclusion, the ambitious goal is to cover a large class of set systems, preserving at the same time the efficiency of the enumeration. Among the existing algorithms, the best-known ones list the maximal subsets in time proportional to their number but may require exponential space. In this paper we improve the state of the art in two directions by introducing an algorithmic framework that, under standard suitable conditions, simultaneously (i) extends the class of problems that can be solved efficiently to strongly accessible set systems, and (ii) reduces the additional space usage from exponential in |U| to stateless, thus accounting for just O(q) space, where q <= |U| is the largest size of a maximal set in F
Recommendations
- scientific article; zbMATH DE number 3857162
- Maximal strongly indexable graphs
- Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs
- Listing all potential maximal cliques of a graph
- scientific article; zbMATH DE number 1500539
- Subgraphs of maximum matching graphs
- Strong list-chromatic index of subcubic graphs
- Finding maximum subgraphs with relatively large vertex connectivity
- On maximum indexable graphs
- scientific article; zbMATH DE number 812041
Cites work
- A New Algorithm for Generating All the Maximal Independent Sets
- A note on the derivation of maximal common subgraphs of two directed or undirected graphs
- A paradigm for listing \((s,t)\)-cuts in graphs
- Algorithm 457: finding all cliques of an undirected graph
- Algorithm Theory - SWAT 2004
- An efficient algorithm for solving pseudo clique enumeration problem
- Arboricity and Subgraph Listing Algorithms
- Computing and Combinatorics
- Database Theory - ICDT 2005
- Efficient enumeration of all minimal separators in a graph
- Enumerating all connected maximal common subgraphs in two graphs
- Enumeration aspects of maximal cliques and bicliques
- Finding maximal common subgraphs via time-space efficient reverse search
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Graph isomorphism in quasipolynomial time (extended abstract)
- scientific article; zbMATH DE number 3957110 (Why is no real title available?)
- scientific article; zbMATH DE number 3737696 (Why is no real title available?)
- scientific article; zbMATH DE number 3742601 (Why is no real title available?)
- scientific article; zbMATH DE number 2081005 (Why is no real title available?)
- Listing all maximal cliques in large sparse real-world graphs
- Listing closed sets of strongly accessible set systems with applications to data mining
- Listing Maximal Independent Sets with Minimal Space and Bounded Delay
- On enumerating all minimal solutions of feedback problems
- On generating all maximal independent sets
- Reverse search for enumeration
- Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
- The complexity of computing the permanent
- The Enumeration of Maximal Cliques of Large Graphs
- The worst-case time complexity for generating all maximal cliques and computational experiments
Cited in
(14)- 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
- 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
- On computing large temporal (unilateral) connected components
- Listing maximal H-free subgraphs
- A linear delay algorithm in SD set system and its application to subgraph enumeration
- Output-sensitive enumeration of maximal cliques in temporal graphs
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
This page was built for publication: Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4631095)
