Skip to Main content Skip to Navigation
Conference papers

Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms

Abstract : This paper investigates the problem of Maximum Common Connected Subgraph (MCCS) which is not necessarily an induced subgraph. This problem has received little attention in the literature which is mainly devoted to the MCIS problem. Two reductions of the MCCS problem to a MCCIS problem are explored: a classic method based on linegraphs and an original approach using subdivision graphs. Then we propose a method to solve MCCS that searchs for a maximum clique in a compatibility graph. To compare with backtrack approach we explore the applicability of Constraint Satisfaction framework to the MCCS problem for both reductions.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00315748
Contributor : Philippe Vismara <>
Submitted on : Friday, August 29, 2008 - 6:47:11 PM
Last modification on : Wednesday, June 3, 2020 - 5:21:46 PM

Identifiers

Collections

Citation

Philippe Vismara, Benoît Valery. Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms. MCO'08: Modelling, Computation and Optimization in Information Systems and Management Sciences, Sep 2008, Metz, France. pp.364-374, ⟨10.1007/978-3-540-87477-5⟩. ⟨lirmm-00315748⟩

Share

Metrics

Record views

137