The maximum common subgraph problem

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Samatova, Nagiza F.
dc.contributor.author Rizk, Mohamad A.
dc.contributor.author Langston, Micheal A.
dc.date.accessioned 2017-03-20T10:11:41Z
dc.date.available 2017-03-20T10:11:41Z
dc.identifier.uri http://hdl.handle.net/10725/5404
dc.description.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. en_US
dc.language.iso en en_US
dc.publisher IEEE en_US
dc.title The maximum common subgraph problem en_US
dc.type Conference Paper / Proceeding en_US
dc.title.subtitle faster solutions via vertex cover en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.keywords Computer science en_US
dc.keywords Mathematics en_US
dc.keywords Coordinate measuring machines en_US
dc.keywords Laboratories en_US
dc.keywords Application software en_US
dc.keywords Scientific computing en_US
dc.keywords US Department of Energy en_US
dc.keywords Research and development en_US
dc.keywords Contracts en_US
dc.keywords Bioinformatics en_US
dc.identifier.doi http://dx.doi.org/10.1109/AICCSA.2007.370907 en_US
dc.identifier.ctation Abu-Khzam, F. N., Samatova, N. F., Rizk, M. A., & Langston, M. A. (2007, May). The maximum common subgraph problem: Faster solutions via vertex cover. In Computer Systems and Applications, 2007. AICCSA'07. IEEE/ACS International Conference on (pp. 367-373). IEEE. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date 13-16 May 2007 en_US
dc.conference.pages 367 - 373 en_US
dc.conference.title IEEE/ACS International Conference on Computer Systems and Applications, 2007 en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url http://ieeexplore.ieee.org/abstract/document/4230982/ en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account