Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
The VF3-Light Subgraph Isomorphism Algorithm: When Doing Less Is More Effective
verfasst von : Vincenzo Carletti, Pasquale Foggia, Antonio Greco, Alessia Saggese, Mario Vento
Erschienen in: Structural, Syntactic, and Statistical Pattern Recognition
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We have recently intoduced VF3, a general-purpose subgraph isomorphism algorithm that has demonstrated to be very effective on several datasets, especially on very large and very dense graphs.
In this paper we show that on some classes of graphs, the whole power of VF3 may become overkill; indeed, by removing some of the heuristics used in it, and as a consequence also some of the data structures that are required by them, we obtain an algorithm that is actually faster.
In order to provide a characterization of this modified algorithm, called VF3-Light, we have performed an evaluation using several kinds of graphs; besides comparing VF3-Light with VF3, we have also compared it to RI, a fast recent algorithm that is based on a similar approach.