Observations from parallelising three maximum common (Connected) subgraph algorithms

Ruth Hoffmann, Ciaran McCreesh*, Samba Ndojh Ndiaye, Patrick Prosser, Craig Reilly, Christine Solnon, James Trimble

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

We discuss our experiences adapting three recent algorithms for maximum common (connected) subgraph problems to exploit multi-core parallelism. These algorithms do not easily lend themselves to parallel search, as the search trees are extremely irregular, making balanced work distribution hard, and runtimes are very sensitive to value-ordering heuristic behaviour. Nonetheless, our results show that each algorithm can be parallelised successfully, with the threaded algorithms we create being clearly better than the sequential ones. We then look in more detail at the results, and discuss how speedups should be measured for this kind of algorithm. Because of the difficulty in quantifying an average speedup when so-called anomalous speedups (superlinear and sublinear) are common, we propose a new measure called aggregate speedup.

Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings
EditorsWillem-Jan van Hoeve
Place of PublicationCham
PublisherSpringer
Pages298-315
Number of pages18
ISBN (Electronic)9783319930312
ISBN (Print)9783319930305
DOIs
Publication statusPublished - 2018
Event15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018 - Delft, Netherlands
Duration: 26 Jun 201829 Jun 2018
Conference number: 15
https://sites.google.com/view/cpaior2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10848
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018
Abbreviated titleCPAIOR
Country/TerritoryNetherlands
CityDelft
Period26/06/1829/06/18
Internet address

Fingerprint

Dive into the research topics of 'Observations from parallelising three maximum common (Connected) subgraph algorithms'. Together they form a unique fingerprint.

Cite this