A Partitioning Algorithm for Maximum Common Subgraph Problems
Authors: Ciaran McCreesh, Patrick Prosser, James Trimble
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show a speedup of more than an order of magnitude over the state of the art, and demonstrate that we can operate on much larger graphs without running out of memory. and We then present an empirical study of the algorithm, demonstrating that it improves the state of the art by more than an order of magnitude on the unlabelled variant of the problem, and showing that it can handle much larger instances than earlier constraint programming or clique approaches due to lower memory usage. |
| Researcher Affiliation | Academia | Ciaran Mc Creesh, Patrick Prosser, James Trimble University of Glasgow, Glasgow, Scotland j.trimble.1@research.gla.ac.uk |
| Pseudocode | Yes | Algorithm 1: Finding a maximum common subgraph. and Algorithm 2: Replacement for lines 11 to 18 of Algorithm 1 to handle directed and edge-labelled cases. |
| Open Source Code | Yes | 1Source code, instances, experimental scripts and raw results are available at https://github.com/jamestrimble/ijcai2017-partitioning-common-subgraph |
| Open Datasets | Yes | Our first set of experiments uses a database of randomly-generated maximum common subgraph instances [Santo et al., 2003; Conte et al., 2007]. and We also ran the algorithms on a set of 5,725 larger instances used in recent studies of subgraph isomorphism [Kotthoff et al., 2016] and maximum common subgraph [Hoffmann et al., 2017]. |
| Dataset Splits | No | The paper mentions datasets like 'randomly-generated maximum common subgraph instances' and 'large subgraph isomorphism instances' but does not specify how these instances were partitioned into training, validation, or test sets for their experiments. |
| Hardware Specification | Yes | Experiments were performed on machines with dual Intel Xeon E5-2640 v2 CPUs and 64GBytes RAM. |
| Software Dependencies | Yes | Our algorithm was implemented1 in C++ and compiled using g++ 5.3.0. |
| Experiment Setup | Yes | Our Select Label Class function chooses a label class with the smallest max( G , H ), breaking ties by selecting a class containing a vertex in G with the largest degree. From the selected class, Select Vertex chooses a vertex in G with maximum degree. and if a time limit of 0.5 seconds per instance were imposed. and a timeout of 1,000 seconds. |