Need graph isomorphism algorithm

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.


--
Posted via http://dbforums.com

re: Need graph isomorphism algorithm

sasha.mal wrote:
[color=blue]
> 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.[/color]

Perhaps a search engine:
http://www.google.com/search?hl=en&i...=Google+Search

Perhaps a graphics newsgroup:
news:comp.graphics

--
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

re: Need graph isomorphism algorithm

On Tue, 14 Oct 2003, Thomas Matthews wrote:[color=blue]
>
> sasha.mal wrote:[color=green]
> >
> > 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.[/color]
>
> Perhaps a search engine:
> http://www.google.com/search?q=graph...hism+%22C++%22
>
> Perhaps a graphics newsgroup:
> news:comp.graphics[/color]

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

re: Need graph isomorphism algorithm

Arthur J. O'Dwyer <ajo@nospam.andrew.cmu.edu> spoke thus:
[color=blue]
> 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.[/color]

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

--
Christopher Benson-Manica | Upon the wheel thy fate doth turn,
ataru(at)cyberspace.org | upon the rack thy lesson learn.

re: Need graph isomorphism algorithm

On Tue, 14 Oct 2003, Christopher Benson-Manica wrote:[color=blue]
>
> Arthur J. O'Dwyer <ajo@nospam.andrew.cmu.edu> spoke thus:[color=green]
> > 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.[/color]
>
> Isn't the graph isomorphism problem one of those lovely NP-hard problems?
> Or something like that?[/color]

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