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
11 months, 2 weeks ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

Can the graph isomorphism problem be solved in polynomial time?

Agnishom Chattopadhyay - 11 months, 2 weeks ago

Log in to reply

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 - 11 months, 2 weeks ago

Log in to reply

Note: Laszlo Babai showed last year that Graph Isomorphism is in Quasipolynomial-time.

Calvin Lin Staff - 11 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...