Finding Maximal Common Subgraphs via Time-Space Efficient Reverse Search - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Finding Maximal Common Subgraphs via Time-Space Efficient Reverse Search

Résumé

For any two given graphs, we study the problem of finding isomorphisms that correspond to inclusion-maximal common induced subgraphs that are connected. While common (induced or not) subgraphs can be easily listed using some well known reduction and state-of-the-art algorithms, they are not guaranteed to be connected. To meet the connectivity requirement, we propose an algorithm that revisits the paradigm of reverse search and guarantees polynomial time per solution (delay) and linear space, on top of showing good practical performance.
Fichier principal
Vignette du fichier
main 2.pdf (364.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01964709 , version 1 (23-12-2018)

Identifiants

Citer

Alessio Conte, Roberto P Grossi, Andrea Marino, Luca P Versari. Finding Maximal Common Subgraphs via Time-Space Efficient Reverse Search. COCOON 2018 - International Computing and Combinatorics Conference, Jul 2018, Qing Dao, China. pp.328-340, ⟨10.1007/978-3-319-94776-1_28⟩. ⟨hal-01964709⟩

Collections

INRIA INRIA2
26 Consultations
130 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More