World's most popular travel blog for travel bloggers.

[Solved]: For how large graphs can we still check for isomorphism?

, , No Comments
Problem Detail: 

Let $G_1,$ $G_2$ be two arbitrary graphs with $n$ vertices and we want to check if they are isomorphic.

Question 1. For what maximal value of $n$ we ​​can actually perform such verification?

Question 2. Is there any result like as a list of all non-isomorphic graphs up to $n$, and what is the value of $n$ — 10, 20?

Asked By : Leox

Answered By : Yuval Filmus

The number of non-isomorphic graphs on $n$ nodes is given by https://oeis.org/A000088. If you only care about connected graphs then it's https://oeis.org/A001349. Programs like nauty can enumerate these graphs for you. That answers your second question.

For your first question, it depends on the meaning on actually. There are algorithms which work for fairly large number of vertices, but fail (take a long time) on some bad examples that supposedly don't happen (or are rare) in practice. The worst-case asymptotic complexity of graph isomorphism is still open. The Wikipedia page has an old (2001) reference which compares real-world algorithms for graph isomorphism. Perhaps you could find a more recent one and update the page.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18358

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback