Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2008

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.
No file

Dates and versions

lirmm-00315748 , version 1 (29-08-2008)

Identifiers

Cite

Philippe Vismara, Benoît Valery. Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms. MCO 2008 - 2nd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, Sep 2008, Metz, France. pp.364-374, ⟨10.1007/978-3-540-87477-5_39⟩. ⟨lirmm-00315748⟩
100 View
0 Download

Altmetric

Share

More