KIT | KIT-Bibliothek | Impressum | Datenschutz

An Optimization Technique for Subgraph Matching Strategies

Batz, Gernot Veit

Abstract:

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.

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000005769
Coverbild
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Forschungsbericht
Jahr 2006
Sprache Englisch
Identifikator ISSN: 1432-7864
urn:nbn:de:swb:90-57691
KITopen-ID: 1000005769
Verlag Universität Karlsruhe, Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2006,7
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page