Skip to Main content Skip to Navigation
New interface
Conference papers

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
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Sunday, December 23, 2018 - 12:15:25 PM
Last modification on : Wednesday, July 6, 2022 - 4:27:28 AM
Long-term archiving on: : Sunday, March 24, 2019 - 12:58:38 PM


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




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⟩



Record views


Files downloads