Paper Info
Title
The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover
Abstract
In the maximum common subgraph (MCS) problem, we are given a pair of graphs and asked to find the largest induced subgraph common to them both. With its plethora of applications, MCS is a familiar and challenging problem. Many algorithms exist that can deliver optimal MCS solutions, but whose asymptotic worst-case run times fail to do better than mere brute-force, which is exponential in the order of the smaller graph. In this paper, we present a faster solution to MCS. We transform an essential part of the search process into the task of enumerating maximal independent sets in only a part of only one of the input graphs. This is made possible by exploiting an efficient decomposition of a graph into a minimum vertex cover and the maximum independent set in its complement. The result is an algorithm whose run time is bounded by a function exponential in the order of the smaller cover rather than in the order of the smaller graph.
Year
DOI
Venue
2007
10.1109/AICCSA.2007.370907
AICCSA
Keywords
Field
DocType
graph theory,vertex functions,maximum common subgraph problem,maximum independent set,minimum vertex cover
Combinatorics,Computer science,Vertex (graph theory),Edge cover,Computer network,Induced subgraph isomorphism problem,Induced subgraph,Theoretical computer science,Vertex cover,Cograph,Subgraph isomorphism problem,Maximal independent set
Conference
ISSN
ISBN
Citations 
2161-5322
1-4244-1031-2
16
PageRank 
References 
Authors
0.95
11
4
Name
Order
Citations
PageRank
Faisal N. Abu Khzam140436.25
Nagiza F. Samatova286174.04
Mohamad A. Rizk3160.95
Michael A. Langston4160.95