Finding smallest partitions of maximal cover on a colored graph using a predefined set of colored subgraphs

This research developed a method for representing colored graphs and an algorithm for searching colored subgraphs that are isomorphic with an input colored graph. Using this tool the research developed a practical algorithm to identify all "smallest" partitions on the input graph of maximal cover such that each set in a partition is a colored subgraph isomorphic to one from the given set of colored subgraphs.; Existing algorithms for detecting subgraphs and identifying isomorphism were reviewed. The work was tested using chemical molecular structures (input colored graph) and a set of molecular lumps (a set of colored subgraphs). The test results can be used as a baseline for further improvements in the algorithm.; This research resulted in an algorithm for finding a greatest characteristic string for any colored graph and a method for partitioning colored graphs using simple heuristics.; From the chemistry perspective---which provided the incentive for this work, the problem can be summarized as facilitating the decomposition of molecules (in their SMILES representation) into their components (Benson Groups), to be able to analyze their thermodynamic properties.; From the computer science perspective, the problem can be summarized as automating the process of generating Benson groups from SMILES representation of a molecule.