An Optimization Technique for Subgraph Matching Strategies
Autor:Gernot Veit Batz
Quelle:Internal Report 2006-7 of the Fakultät für Informatik, Universität Karlsruhe (TH); October 2006; ISSN: 1432-7864
Subgraph matching (aka graph pattern matching or the subgraph
isomorphism problem) is NP-complete. But in practice subgraph
matching should be performed in reasonable time if possible.
In this work a heuristically optimizing approach to subgraph
matching on labeled graphs is described. It relies on the fact
that the runtime of the matching process can vary significantly
for different matching strategies. The finding of a good
matching strategy is stated as an optimization problem which is
solved heuristically. The cost model for the possible matching
strategies takes the structure of the present host graph into
account. The necessary information can be obtained by an
analysis of the host graph.
