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.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-01964709
Contributor : Marie-France Sagot <>
Submitted on : Sunday, December 23, 2018 - 12:15:25 PM
Last modification on : Tuesday, February 26, 2019 - 10:54:02 AM
Document(s) archivé(s) le : Sunday, March 24, 2019 - 12:58:38 PM

File

main 2.pdf
Files produced by the author(s)

Identifiers

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. pp.328-340, ⟨10.1007/978-3-319-94776-1_28⟩. ⟨hal-01964709⟩

Share

Metrics

Record views

15

Files downloads

138