tag:blogger.com,1999:blog-8039905363673116148.post4196328134994753383..comments2022-03-25T04:22:14.078-07:00Comments on comments on Andrew Dalke's writings: Topologically non-planar moleculesAndrew Dalkehttp://www.blogger.com/profile/17091314849699854287noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8039905363673116148.post-42489607746387918972012-05-26T04:28:16.287-07:002012-05-26T04:28:16.287-07:00Hi nlskrg,
Researching now, I see that the MCS is...Hi nlskrg,<br /><br />Researching now, I see that the MCS is polynomial for outerplanar graphs, and for trees, but it is NP for planar graphs. One paper says "The maximum common subgraph problem is NP-hard even for planar graphs of bounded degree 3 (Garey and Johnson, 1979) "<br /><br />Thanks for the correction!Andrew Dalkehttps://www.blogger.com/profile/17091314849699854287noreply@blogger.comtag:blogger.com,1999:blog-8039905363673116148.post-29425992608334768752012-05-26T03:56:11.524-07:002012-05-26T03:56:11.524-07:00Is there an article stating that MCS is solvable i...Is there an article stating that MCS is solvable in polynomial-time for planar molecular graphs? The subgraph isomorphism problem is NP-complete even for connected planar graphs of bounded-degree. Hence, planarity (also combined with the bounded-degree property of molecular graphs) seems not be sufficient to attain a polynomial-time MCS algorithm (unless P=NP).nlskrghttps://www.blogger.com/profile/13912306704306845870noreply@blogger.com