The Complexity of Mining Maximal Frequent Subgraphs
Summary: Maps complexity of enumerating maximal frequent subgraphs for connected graph classes and labeled vs unlabeled variants under bounded support or bounded output-size. For labeled instances bounded support yields tractability (bounded output often doesn't, except labeled trees where either bound suffices); unlabeled instances are harder—NP-complete even for two unlabeled trees with support=output=2. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,347 | A Relational Framework for Classifier Engineering | 2017 | PODS | 5.1019568e-05 |
| 10,361 | The Complexity of Maximal Common Subsequence Enumeration | 2025 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,073 | Finding and Approximating Top-k Answers in Keyword Proximity Search | 2006 | PODS | 0.00014264992 |
| 3,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.6248763e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,854 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD | 5.3006473e-05 |
| 11,060 | Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs | 2024 | VLDB | 4.1945683e-05 |
| 1,650 | Efficient Enumeration of Maximal k-Plexes | 2015 | SIGMOD | 0.00011013428 |
| 2,512 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 8.6196023e-05 |
| 9,935 | Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach | 2025 | SIGMOD | 4.2482599e-05 |
| 10,848 | Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds | 2025 | VLDB | 4.1945683e-05 |
| 6,207 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 5.1572428e-05 |
| 6,406 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0765917e-05 |
| 9,565 | Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs | 2017 | SIGMOD | 4.3254416e-05 |
| 10,361 | The Complexity of Maximal Common Subsequence Enumeration | 2025 | PODS | 4.1945683e-05 |