8
$\begingroup$

While studying data structures i was told my instructor that even i am given 3 hour/30 days/3 years to find out whether two graphs are isomorphic or not, it is very very complex and even after spending this much amount of time i will not able to figure out clearly whether the given two graphs are isomorphic or not. It is NP-complete problem.

So i got the curiosity that why i am studying it then. What could be the possible applications of such isomorphic graphs which can be solved ?

  • 7
    Graph isomorphism is not known to be NP-complete. Wikipedia says "[i]ts practical applications include primarily cheminformatics, mathematical chemistry (identification of chemical compounds), and electronic design automation (verification of equivalence of various representations of the design of an electronic circuit)."2012-03-15
  • 0
    @QiaochuYuan : well, i was told by my instructor today that it is class NP problem. That's why i posted my confusion here...2012-03-15
  • 9
    "NP" does not mean "NP-complete," although I guess this is an understandable mistake; graph isomorphism is one of the few problems in NP not known to either be in P or be NP-complete along with factoring.2012-03-15
  • 0
    @QiaochuYuan : ok. I am aware of neither NP or NP complex problem. I just heard that so that i posted right here. I am editing the post for it.2012-03-15
  • 1
    The term is "NP-complete", not "NP complex".2012-03-15
  • 0
    What precisely is your question?2012-03-15
  • 0
    @Azoo : what can be the applications of the isomorphic graphs?2012-03-15
  • 0
    You mean what is the application of the isomorphism problem in practice?2012-03-15
  • 0
    In my opinion it is important very often to determine when two graphs are NOT isomorphic, but that is exactly the same problem....2012-03-15

4 Answers 4