Maximum common induced subgraph parameterized by vertex cover

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.date.accessioned 2015-12-07T13:19:04Z
dc.date.available 2015-12-07T13:19:04Z
dc.date.copyright 2014
dc.date.issued 2015-12-07
dc.identifier.issn 0020-0190 en_US
dc.identifier.uri http://hdl.handle.net/10725/2780
dc.description.abstract The Maximum Common Induced Subgraph problem (MCIS ) takes a pair of graphs as input and asks for a graph of maximum order that is isomorphic to an induced subgraph of each of the input graphs. The problem is NP-hard in general, and remains so on many graph classes including graphs of bounded treewidth. In the framework of parameterized complexity, the latter assertion means that MCIS is W[1]-hard when parameterized by the treewidths of input graphs. A classical graph parameter that has been used recently in many parameterization problems is Vertex Cover. In this paper we prove constructively that MCIS is fixed-parameter tractable when parameterized by the vertex cover numbers of the input graphs. Our algorithm is also an improved exact algorithm for the problem on instances where the minimum vertex cover is small compared to the order of input graphs. en_US
dc.language.iso en en_US
dc.title Maximum common induced subgraph parameterized by vertex cover en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Information Processing Letters en_US
dc.journal.volume 114 en_US
dc.journal.issue 3 en_US
dc.article.pages 99-103 en_US
dc.keywords Graph algorithms en_US
dc.keywords Vertex cover en_US
dc.keywords Common subgraph isomorphism en_US
dc.keywords Maximum common subgraph en_US
dc.keywords Fixed-parameter tractability en_US
dc.identifier.doi http://dx.doi.org/10.1016/j.ipl.2013.11.007 en_US
dc.identifier.ctation Abu-Khzam, F. N. (2014). Maximum common induced subgraph parameterized by vertex cover. Information Processing Letters, 114(3), 99-103. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S0020019013002755
dc.orcid.id https://orcid.org/0000-0001-5221-8421

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account