The maximum common subgraph problem
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 asympt...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5404 http://dx.doi.org/10.1109/AICCSA.2007.370907 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://ieeexplore.ieee.org/abstract/document/4230982/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513476280451072 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Samatova, Nagiza F. Rizk, Mohamad A. Langston, Micheal A. |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Samatova, Nagiza F. Rizk, Mohamad A. Langston, Micheal A. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Samatova, Nagiza F. Rizk, Mohamad A. Langston, Micheal A. |
| dc.date.none.fl_str_mv | 2017-03-20T10:11:41Z 2017-03-20T10:11:41Z 2017-03-20 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/5404 http://dx.doi.org/10.1109/AICCSA.2007.370907 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. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://ieeexplore.ieee.org/abstract/document/4230982/ |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | IEEE |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | The maximum common subgraph problem faster solutions via vertex cover |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_f535c05766f6bd7525f8a4bb0b23d372 |
| identifier_str_mv | 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/5404 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | IEEE |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | The maximum common subgraph problemfaster solutions via vertex coverAbu-Khzam, Faisal N.Samatova, Nagiza F.Rizk, Mohamad A.Langston, Micheal A.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.N/AIEEE2017-03-20T10:11:41Z2017-03-20T10:11:41Z2017-03-20Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/5404http://dx.doi.org/10.1109/AICCSA.2007.370907Abu-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.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://ieeexplore.ieee.org/abstract/document/4230982/eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/54042021-03-19T10:00:51Z |
| spellingShingle | The maximum common subgraph problem Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | The maximum common subgraph problem |
| title_full | The maximum common subgraph problem |
| title_fullStr | The maximum common subgraph problem |
| title_full_unstemmed | The maximum common subgraph problem |
| title_short | The maximum common subgraph problem |
| title_sort | The maximum common subgraph problem |
| url | http://hdl.handle.net/10725/5404 http://dx.doi.org/10.1109/AICCSA.2007.370907 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://ieeexplore.ieee.org/abstract/document/4230982/ |