From: Efficient enumeration of monocyclic chemical graphs with given path frequencies
Entry | Â | Â | Â | 2-Phase Algorithm | Our Algorithm | Â | |||||
---|---|---|---|---|---|---|---|---|---|---|---|
Formula | n | w | K | Tree | Time | Time/graph | Tree | Cycle | Time | Time/graph | Ratio |
 |  | 1 | 3 | 14 | 0.009 | 643.9E-6 | 14 | 5 | 0.014 | 736.8E-6 | 1.1 |
 |  | 2 | 3 | 49 | 0.009 | 183.7E-6 | 49 | 14 | 0.017 | 269.8E-6 | 1.5 |
D08040 | Â | 3 | 3 | 58 | 0.009 | 155.2E-6 | 58 | 21 | 0.017 | 215.1E-6 | 1.4 |
C5H9N3 | 8 | 4 | 3 | 60 | 0.009 | 150.0E-6 | 60 | 25 | 0.017 | 200.0E-6 | 1.3 |
 |  | 5 | 3 | 60 | 0.009 | 150.0E-6 | 60 | 26 | 0.017 | 197.6E-6 | 1.3 |
 |  | 50 | 3 | 61 | 0.003 | 49.2E-6 | 61 | 28 | 0.017 | 191.0E-6 | 3.9 |
 |  | 1 | 3 | 30 | 0.017 | 566.7E-6 | 30 | 1,318 | 0.170 | 126.1E-6 | 0.2 |
 |  | 2 | 3 | 313 | 0.024 | 76.7E-6 | 313 | 8,822 | 0.266 | 29.1E-6 | 0.4 |
D00332 | Â | 3 | 3 | 1,327 | 0.024 | 76.7E-6 | 1,327 | 18,010 | 0.285 | 14.7E-6 | 0.8 |
C9H17NO2 | 12 | 4 | 3 | 2,239 | 0.025 | 11.2E-6 | 2,239 | 24,550 | 0.293 | 10.9E-6 | 1.0 |
 |  | 5 | 3 | 4,197 | 0.025 | 6.0E-6 | 4,197 | 30,122 | 0.297 | 8.7E-6 | 1.5 |
 |  | 50 | 3 | 6,656 | 0.025 | 3.8E-6 | 6,656 | 34,145 | 0.309 | 7.6E-6 | 2.0 |
 |  | 1 | 3 | 4,590 | 4.115 | 896.5E-6 | 4,590 | 6,511 | 70.806 | 6.4E-3 | 3.8 |
 |  | 2 | 3 | 76,901 | 10.466 | 136.1E-6 | 76,901 | 186,971 | 221.353 | 838.7E-6 | 6.2 |
D00555 | Â | 3 | 3 | 221,492 | 14.952 | 67.5E-6 | 221,492 | 770,625 | 317.488 | 320.0E-6 | 4.7 |
C11H18N2O3 | 16 | 4 | 3 | 348,335 | 16.381 | 47.0E-3 | 348,335 | 1,307,167 | 347.379 | 209.8E-6 | 4.5 |
 |  | 5 | 3 | 458,635 | 16.837 | 36.7E-3 | 458,635 | 1,976,544 | 357.252 | 146.7E-6 | 4.0 |
 |  | 50 | 3 | 556,272 | 17.090 | 30.7E-3 | 556,272 | 3,544,713 | 363.743 | 88.7E-6 | 2.9 |
 |  | 1 | 3 | ≥1,134,806 | T.O. | 1.6E-3 | ≥21,048 | ≥0 | T.O. | 85.5E-3 | 53.4 |
 |  | 2 | 3 | ≥3,917,059 | T.O. | 459.5E-6 | ≥0 | ≥0 | T.O. | – | – |
D00079 |  | 3 | 3 | ≥86,360 | T.O. | 20.8E-3 | ≥28,187 | ≥0 | T.O. | 64.6E-3 | 3.1 |
C20H32O5 | 25 | 4 | 3 | ≥1,469,428 | T.O. | 1.2E-3 | ≥61,929 | ≥229 | T.O. | 29.0E-3 | 24.2 |
 |  | 5 | 3 | ≥5,118,134 | T.O. | 351.7E-6 | ≥19,900 | ≥1,726 | T.O. | 83.2E-3 | 236.6 |
 |  | 50 | 3 | ≥216,008,008 | T.O. | 8.3E-6 | ≥0 | ≥0 | T.O. | – | – |