Learning to Bound for Maximum Common Subgraph Algorithms

Simple item page
dc.citation.issueArticle No 22
dc.citation.volume340
dc.contributor.authorKothalawala BW
dc.contributor.authorKoehler H
dc.contributor.authorWang Q
dc.contributor.editorGarcia de la Banda M
dc.coverage.spatialGlasgow, Scotland
dc.date.accessioned2025-08-26T01:52:18Z
dc.date.available2025-08-26T01:52:18Z
dc.date.finish-date2025-08-15
dc.date.issued2025-08-08
dc.date.start-date2025-08-10
dc.description.abstractIdentifying the maximum common subgraph between two graphs is a computationally challenging NP-hard problem. While the McSplit algorithm represents a state-of-the-art approach within a branch-and-bound (BnB) framework, several extensions have been proposed to enhance its vertex pair selection strategy, often utilizing reinforcement learning techniques. Nonetheless, the quality of the upper bound remains a critical factor in accelerating the search process by effectively pruning unpromising branches. This research introduces a novel, more restrictive upper bound derived from a detailed analysis of the McSplit algorithm's generated partitions. To enhance the effectiveness of this bound, we propose a reinforcement learning approach that strategically directs computational effort towards the most promising regions within the search space.
dc.description.confidentialfalse
dc.format.pagination22:1-22:18
dc.identifier.citationKothalawala BW, Koehler H, Wang Q. (2025). Learning to Bound for Maximum Common Subgraph Algorithms. Garcia de la Banda M. Leibniz International Proceedings in Informatics Lipics. (pp. 22:1-22:18). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany.
dc.identifier.doi10.4230/LIPIcs.CP.2025.22
dc.identifier.elements-typec-conference-paper-in-proceedings
dc.identifier.issn1868-8969
dc.identifier.urihttps://mro.massey.ac.nz/handle/10179/73420
dc.publisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
dc.publisher.urihttp://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.22
dc.rights(c) 2025 The Author/s
dc.rightsCC BY 4.0
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.source.journalLeibniz International Proceedings in Informatics Lipics
dc.source.name-of-conference31st International Conference on Principles and Practice of Constraint Programming (CP 2025)
dc.subjectCombinatorial Search
dc.subjectBranch and Bound
dc.subjectGraph Theory
dc.titleLearning to Bound for Maximum Common Subgraph Algorithms
dc.typeconference
pubs.elements-id502790
pubs.organisational-groupOther
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
502790 PDF.pdf
Size:
1.5 MB
Format:
Adobe Portable Document Format
Description:
Published version.pdf
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
9.22 KB
Format:
Plain Text
Description:
Download
Collections
Conference Papers