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,345 | A Relational Framework for Classifier Engineering | 2017 | PODS | 5.0970607e-05 |
| 10,373 | The Complexity of Maximal Common Subsequence Enumeration | 2025 | PODS | 4.1905499e-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,072 | Finding and Approximating Top-k Answers in Keyword Proximity Search | 2006 | PODS | 0.00014256848 |
| 3,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.620459e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,903 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD | 5.2757528e-05 |
| 11,063 | Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs | 2024 | VLDB | 4.1905499e-05 |
| 1,650 | Efficient Enumeration of Maximal k-Plexes | 2015 | SIGMOD | 0.00011002771 |
| 2,516 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 8.6114467e-05 |
| 9,936 | Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach | 2025 | SIGMOD | 4.2441896e-05 |
| 10,852 | Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds | 2025 | VLDB | 4.1905499e-05 |
| 6,206 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 5.1522897e-05 |
| 6,386 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0820608e-05 |
| 9,564 | Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs | 2017 | SIGMOD | 4.3212967e-05 |
| 10,373 | The Complexity of Maximal Common Subsequence Enumeration | 2025 | PODS | 4.1905499e-05 |