The maximum common subgraph problem has been proven to have NP-hard complexity. Despite this theoretical limit, state-of-the-art algorithms made it viable to solve the problem exactly for some applications. This thesis discusses improvements to the state-of-the-art (a branch and bound algorithm with a smart partitioning strategy) in two areas: the generalization of the algorithm to handle sets of graphs and a best-first search space exploration strategy. The original algorithm is not well suited to serve applications where time is constrained, and approximate solutions can be accepted, as it is designed to explore the solution space exhaustively. The proposed heuristics aim to achieve better approximate solutions in time-bounded problem instances.