Need graph isomorphism algorithm

Discussion in 'C Programming' started by sasha.mal, Oct 11, 2003.

  1. sasha.mal

    sasha.mal Guest

    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
    sasha.mal, Oct 11, 2003
    #1
    1. Advertising

  2. sasha.mal wrote:

    > 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:
    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
    Thomas Matthews, Oct 14, 2003
    #2
    1. Advertising

  3. On Tue, 14 Oct 2003, Thomas Matthews wrote:
    >
    > sasha.mal wrote:
    > >
    > > 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.

    >
    > 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
    Arthur J. O'Dwyer, Oct 14, 2003
    #3
  4. [OT] graph isomorphism

    Arthur J. O'Dwyer <> spoke thus:

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

    --
    Christopher Benson-Manica | Upon the wheel thy fate doth turn,
    ataru(at)cyberspace.org | upon the rack thy lesson learn.
    Christopher Benson-Manica, Oct 14, 2003
    #4
  5. Re: [OT] graph isomorphism

    On Tue, 14 Oct 2003, Christopher Benson-Manica wrote:
    >
    > Arthur J. O'Dwyer <> spoke thus:
    > > 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?


    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
    Arthur J. O'Dwyer, Oct 14, 2003
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. sasha.mal
    Replies:
    0
    Views:
    343
    sasha.mal
    Oct 11, 2003
  2. George Sakkis
    Replies:
    1
    Views:
    450
    Szabolcs Nagy
    Jan 29, 2007
  3. Dr Ann Huxtable

    Missing Graph.h and (Graph.lib) woes - any help

    Dr Ann Huxtable, Dec 21, 2004, in forum: C Programming
    Replies:
    6
    Views:
    650
    Dr Ann Huxtable
    Dec 21, 2004
  4. Jef Driesen
    Replies:
    3
    Views:
    2,543
    mlimber
    Jan 24, 2006
  5. Emilio Mayorga
    Replies:
    6
    Views:
    331
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page