Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00315748
Déposant : Philippe Vismara <>
Soumis le : vendredi 29 août 2008 - 18:47:11
Dernière modification le : mercredi 3 juin 2020 - 17:21:46

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. pp.364-374, ⟨10.1007/978-3-540-87477-5⟩. ⟨lirmm-00315748⟩

Partager

Métriques

Consultations de la notice

137