Finding Maximal Common Subgraphs via Time-Space Efficient Reverse Search

Abstract : 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.
Type de document :
Communication dans un congrès
COCOON 2018 - International Computing and Combinatorics Conference, Jul 2018, Qing Dao, China. 10976, pp.328-340, 2018, Lecture Notes in Computer Science. 〈10.1007/978-3-319-94776-1_28〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01964709
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 23 décembre 2018 - 12:15:25
Dernière modification le : jeudi 7 février 2019 - 15:36:53

Fichier

main 2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

8

Téléchargements de fichiers

89