Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries
Summary: Introduces dual-symmetry breaking for exact MCS, exploiting modular symmetries in both variable and value graphs via local neighborhoods. Prunes isomorphic search subtrees while preserving optimality, substantially outperforming RRSplit on benchmarks. (summarized by gpt-5.6-luna on Jul 26 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Buddhi Kothalawala (The Australian National University)
- 2. Henning Koehler (Massey University)
- 3. Muhammad Farhan (The Australian National University)
BibTeX Citation
@inproceedings{kothalawala_sigmod26,
title = {{Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries}},
author = {Kothalawala, Buddhi and Koehler, Henning and Farhan, Muhammad},
series = {{SIGMOD} '26},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3802005},
url = {https://dl.acm.org/doi/10.1145/3802005},
year = {2026}
}
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,758 | Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach | 2025 | SIGMOD | 6.0972035e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,407 | Theoretically and Practically Efficient Maximum Biclique Search | 2026 | SIGMOD |
| 2 | 4,853 | Efficient Subgraph Search over Large Uncertain Graphs | 2011 | VLDB |
| 3 | 6,520 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB |
| 4 | 9,540 | Efficient Maximum s-Bundle Search via Local Vertex Connectivity | 2025 | SIGMOD |
| 5 | 7,522 | The Complexity of Mining Maximal Frequent Subgraphs | 2013 | PODS |
| 6 | 3,709 | Multi-Query Optimization for Subgraph Isomorphism Search | 2017 | VLDB |
| 7 | 7,032 | Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach | 2023 | SIGMOD |
| 8 | 10,204 | Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching | 2026 | SIGMOD |
| 9 | 3,522 | A Partition-Based Approach to Structure Similarity Search | 2014 | VLDB |
| 10 | 5,758 | Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach | 2025 | SIGMOD |