Need graph isomorphism algorithm

[sasha.mal]

Hello everybody!



Could anyone help with a practical graph isomorphism algorithm, coded
in C++ (C would also do), to work with genus bounded graphs of a
bounded degree.

Currently, any algorithm to work with planar graphs with degree bounded
by 4 (on a quadratic grid) would also help.



Thanks a lot,

Alex.

 

[Thomas Matthews]

Hello everybody!

Could anyone help with a practical graph isomorphism algorithm, coded
in C++ (C would also do), to work with genus bounded graphs of a
bounded degree.

Currently, any algorithm to work with planar graphs with degree bounded
by 4 (on a quadratic grid) would also help.

Thanks a lot,

Alex.

Perhaps a search engine:
http://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=graph+isomorphism+"C++"&btnG=Google+Search

Perhaps a graphics newsgroup:

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Arthur J. O'Dwyer]

Perhaps a search engine:
http://www.google.com/search?q=graph+isomorphism+"C++"

Perhaps a graphics newsgroup:
news:comp.graphics

Okay, I wasn't going to post to this thread, seeing as all I know about
graph isomorphism is that it's hard, and since I recognize 'sasha.mal'
from sci.math (or was it rec.puzzles?) I'm fairly sure he knows that.

But do you know something I don't? What would comp.graphics know about
graph isomorphism -- does it have some common application in graphics
programming? Pray elucidate!

(Sasha, try comp.programming on this one.)

-Arthur

 

[Christopher Benson-Manica]

Okay, I wasn't going to post to this thread, seeing as all I know about
graph isomorphism is that it's hard, and since I recognize 'sasha.mal'
from sci.math (or was it rec.puzzles?) I'm fairly sure he knows that.

Isn't the graph isomorphism problem one of those lovely NP-hard problems? Or
something like that?

 

[Arthur J. O'Dwyer]

Isn't the graph isomorphism problem one of those lovely NP-hard problems?
Or something like that?

Almost. AIUI from a brief tour of MathWorld, graph isomorphism

is in NP (of course)
is not known to be in P
is not known to be NP-complete

so it's not known to be NP-hard. Up until now, I've been kind of
colloquially using the English word "hard" to denote "not known to
be in P" (i.e., "not easy" , but I suppose I should know to be
more precise.

[There *are* apparently a *lot* of problems reducible to graph
isomorphism, but AFAICT the problem isn't known to be NP-complete.]

-Arthur