Subscribe to:
Post Comments (Atom)
skip to main |
skip to sidebar
About Me
- Andrew Dalke
- I am an American living in Göteborg, Sweden. I make my living writing software for computational chemistry and biology, usually in Python.
2 comments:
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).
Hi nlskrg,
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) "
Thanks for the correction!
Post a Comment