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.
Type de document :
Communication dans un congrès
MCO'08: Modelling, Computation and Optimization in Information Systems and Management Sciences, Sep 2008, Metz, France. Springer Berlin Heidelberg, pp.364-374, 2008, Communications in Computer and Information Science. 〈10.1007/978-3-540-87477-5_39〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00315748
Contributeur : Philippe Vismara <>
Soumis le : vendredi 29 août 2008 - 18:47:11
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

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. Springer Berlin Heidelberg, pp.364-374, 2008, Communications in Computer and Information Science. 〈10.1007/978-3-540-87477-5_39〉. 〈lirmm-00315748〉

Partager

Métriques

Consultations de la notice

97