Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach
Summary: RRSplit is a redundancy-reduced backtracking algorithm for maximum common subgraph search. It introduces reductions and upper bounds to prune unpromising branches, providing a worst-case guarantee matching the best-known bound while delivering substantial practical speedups over McSplit. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Kaiqiang Yu (Nanyang Technological University)
- 2. Kaixin Wang (Beijing Institute of Technology)
- 3. Cheng Long (Nanyang Technological University)
- 4. Laks Lakshmanan (University of British Columbia)
- 5. Reynold Cheng (University of Hong Kong)
BibTeX Citation
@inproceedings{yu_sigmod25,
title = {{Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach}},
author = {Yu, Kaiqiang and Wang, Kaixin and Long, Cheng and Lakshmanan, Laks and Cheng, Reynold},
series = {{SIGMOD} '25},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3725404},
url = {https://dl.acm.org/doi/10.1145/3725404},
year = {2025}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,187 | Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries | 2026 | SIGMOD | 5.093636e-05 |
| 10,287 | Shape-Agnostic Table Overlap Discovery: A Maximum Common Subhypergraph Approach | 2026 | SIGMOD | 5.093636e-05 |
| 10,419 | A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] | 2026 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 12 of 12 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next