2007 TheMaximumCommonSubgraphProblem

• (Abu-Khzam et al., 2007) ⇒ Faisal N. Abu-Khzam, Nagiza F. Samatova, Mohamad A. Rizk, and Michael A. Langston. (2007). “The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover.” In: Proceedings of 2007 IEEE/ACS International Conference on Computer Systems and Applications. doi:10.1109/AICCSA.2007.370907

Subject Headings: Maximum Common Subgraph; Maximum Common Subgraph Algorithm; Maximum Common Subgraph Task; Maximum Common Subgraph System.

Cited By

• http://scholar.google.com/scholar?q=%222007%22+The+Maximum+Common+Subgraph+Problem%3A+Faster+Solutions+via+Vertex+Cover

Quotes

Author Keywords

• Graph Theory; Vertex Function; Maximum Common Subgraph Problem; Maximum Independent Set; Minimum 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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2007 TheMaximumCommonSubgraphProblem	Faisal N. Abu-Khzam Nagiza F. Samatova Mohamad A. Rizk Michael A. Langston			The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover				10.1109/AICCSA.2007.370907		2007