In this paper we introduce VF3-Light, a simplification of VF3, a recently introduced, general-purpose subgraph isomorphism algorithm. While VF3 has demonstrated to be very effective on several datasets, especially on very large and very dense graphs, we will show that on some classes of graphs, the full power of VF3 may become an 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 (VF3-Light) that is actually faster. In order to provide a characterization of this modified algorithm, we have performed an evaluation using several publicly available graph datasets. Besides comparing VF3-Light with VF3, we have also included in the comparison other recent algorithms that are rated among the fastest in the state of the art.

VF3-Light: A lightweight subgraph isomorphism algorithm and its experimental evaluation

Carletti Vincenzo
Project Administration
;
Foggia Pasquale
Supervision
;
Greco Antonio
Investigation
;
Vento Mario
Project Administration
;
Vigilante Vincenzo
Software
2019

Abstract

In this paper we introduce VF3-Light, a simplification of VF3, a recently introduced, general-purpose subgraph isomorphism algorithm. While VF3 has demonstrated to be very effective on several datasets, especially on very large and very dense graphs, we will show that on some classes of graphs, the full power of VF3 may become an 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 (VF3-Light) that is actually faster. In order to provide a characterization of this modified algorithm, we have performed an evaluation using several publicly available graph datasets. Besides comparing VF3-Light with VF3, we have also included in the comparison other recent algorithms that are rated among the fastest in the state of the art.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4725821
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact