Waste less time on Facebook — follow Brilliant.
×

Graph Isomorphism

The graph isomorphism problem has a long history in the fields of computer science, mathematics and chemistry. Graph isomorphism is very important due to its practical applications and its unique complexity theoretic status . Informally, graph isomorphism is to check if two graphs that look different are actually the same. More formally, given two graphs does there exist a 1-to-1 mapping of vertices in one graph onto the vertices of other such that edges and non-edges are preserved?. Example of two isomorphic graphs is given below

A more interesting example is below

Some of the applications of Graph Isomorphism are verification of computer programs, Security, for example fingerprint scanners, facial scanners etc. The problem is in class NP (nondeterministic polynomial time) mean given a solution (bijective mapping) you can verify the solution efficiently.

Note by Shivdutt Sharma
7 months, 2 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Can the graph isomorphism problem be solved in polynomial time? Agnishom Chattopadhyay · 7 months, 2 weeks ago

Log in to reply

@Agnishom Chattopadhyay till now no one is able to solve the problem in polynomial time in general (For some special class of graphs it is solvable in polynomial time like for trees) Shivdutt Sharma · 7 months, 2 weeks ago

Log in to reply

@Shivdutt Sharma Note: Laszlo Babai showed last year that Graph Isomorphism is in Quasipolynomial-time. Calvin Lin Staff · 7 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...