Loading ...
Sorry, an error occurred while loading the content.

Re: [hackers-il] Updated version of Graph Isomorphism Algorithm

Expand Messages
  • Nadav Har'El
    ... Ok ;) Though I have to warn you - the hackers-il mailing-list isn t exactly a known group of graph-algorithmers, so saying I mailed it to hackers-il
    Message 1 of 12 , Dec 1, 2000
    • 0 Attachment
      On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
      > Well part of the reason that I post the versions here is so that I'll have
      > prior art claims. I don't plan to patent the algorithm, but I wish to be
      > credited for it. Otherwise, I also wish to receive feedback for it.

      Ok ;) Though I have to warn you - the hackers-il mailing-list isn't exactly
      a known group of graph-algorithmers, so saying "I mailed it to hackers-il
      first" wouldn't give you much against another researcher who sent his research
      to an accredited journal...

      > > By the way, I assume you studied Graph Algorithms in the Technion, and read
      > > a book about it, like Shimon Even's great "Graph Algorithms", right? If not,
      > > this would certainly be the first step before dabbling in graph algorithms ;)
      > I took a course of the Electrical Engineering faculty named "Intro to Data
      > Structures and Algorithms" which covers graph algorithms among other
      > things. There weren't too many proves there, though. I also once took a
      > correspondence course for Youth about graph theory. I glanced through the
      > first chapter of Even's book, but did not read it thouroughly yet.

      If you're interested in the subject, I wholeheartedly recommend reading
      Prof. Even's book, even though it is not an easy undertaking. That book is
      now out-of-print, but you can try getting it in the Technion library.
      I don't know what they teach in "Intro to Data Structures and Algorithms",
      but Even teaches his "Algorithms in Graph Theory" course following his
      book almost exactly, so if you read the book you'll know everything they
      teach in the Technion's CS "Algorithms in Graph Theory" course.

      > Anyway, I did meet with Prof. Even's last Monday, and he noted why the
      > initial version of the alogirthm would not always work. I deduced other
      > cases why the later versions wouldn't work based on his example. It is my
      > intention to meet him next Monday (at his office hours) and present to him
      > the most recent version and ask for his opinion and input.

      That's good :) I don't want to doubt the inteligence of myself and other
      people in this list, but let's just say that Prof. Even is probably an
      order-of-magnitude better in Graph Theory then the rest of us, so if you
      got him to help you, that is great.

      > I don't think this discussion is off topic, but if enough people are fed
      > up with it, I will lower the posting rate.

      Don't worry - even if you send an daily update it won't bother me too much ;)
      But I was just trying to suggest to you a more productive method than sending
      us an update each day. I don't know about the other people of the mailing
      list, but I know that I don't have patience to read your code every day, try
      to see what changed, and what is still wrong with the algorithm, etc., so I
      doubt I'll be able to help you much...

      --
      Nadav Har'El | Friday, Dec 1 2000, 4 Kislev 5761
      nyh@... |-----------------------------------------
      Phone: +972-53-245868, ICQ 13349191 |Tea or coffee? Coffee, without cream. It
      http://nadav.harel.org.il |will be without milk, we have no cream.
    • Shlomi Fish
      ... Yes, but what if I posted this today, and a month later the letter with the Algorithm description was received in the Journal s office, and it was
      Message 2 of 12 , Dec 1, 2000
      • 0 Attachment
        On Fri, 1 Dec 2000, Nadav Har'El wrote:

        > On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
        > > Well part of the reason that I post the versions here is so that I'll have
        > > prior art claims. I don't plan to patent the algorithm, but I wish to be
        > > credited for it. Otherwise, I also wish to receive feedback for it.
        >
        > Ok ;) Though I have to warn you - the hackers-il mailing-list isn't exactly
        > a known group of graph-algorithmers, so saying "I mailed it to hackers-il
        > first" wouldn't give you much against another researcher who sent his research
        > to an accredited journal...
        >

        Yes, but what if I posted this today, and a month later the letter with
        the Algorithm description was received in the Journal's office, and it was
        published six or 8 weeks later. Obviously, I am the one who came up with
        the algorithm first.

        Regards,

        Shlomi Fish


        ----------------------------------------------------------------------
        Shlomi Fish shlomif@...
        Home Page: http://t2.technion.ac.il/~shlomif/
        Home E-mail: shlomif@...

        The prefix "God Said" has the extraordinary logical property of
        converting any statement that follows it into a true one.
      • Nadav Har'El
        ... Unfortunately, this is not exactly how the academic world works... I mean, consider the editor of some world-renowned graph-algorithm journal (I have to
        Message 3 of 12 , Dec 1, 2000
        • 0 Attachment
          On Fri, Dec 01, 2000, Shlomi Fish wrote about "Re: [hackers-il] Updated version of Graph Isomorphism Algorithm":
          > > Ok ;) Though I have to warn you - the hackers-il mailing-list isn't exactly
          > > a known group of graph-algorithmers, so saying "I mailed it to hackers-il
          > > first" wouldn't give you much against another researcher who sent his research
          > > to an accredited journal...
          >
          > Yes, but what if I posted this today, and a month later the letter with
          > the Algorithm description was received in the Journal's office, and it was
          > published six or 8 weeks later. Obviously, I am the one who came up with
          > the algorithm first.

          Unfortunately, this is not exactly how the academic world works... I mean,
          consider the editor of some world-renowned graph-algorithm journal (I have
          to admit that I don't know the name of one...). If in a month he'll get
          from somebody else a submittion of an article with your algorithm in it,
          he'll do his best to make sure that this algorithm wasn't published before -
          including giving giving the submitted paper to referees familiar with the
          subject to look at it. But none of them read hackers-il, and none of them
          will know that you have previously published the same algorithm in hackers-il.
          So they print the article, and every graph-algorithmist in the world reads
          this paper, and the algorithm becomes known as TheOtherGuy's algorithm.
          Several months later you find this published paper, and write the editor
          telling him you invented the algorithm before that - and you have the proof
          in hackers-il's archives. What do you think they'll do? The most they'll do
          is publish a short note, but the algorithm will still be known as TheOtherGuy's
          algorithm.
          This is why you'll see people in Academia publishing several papers a year,
          many of them with only small contributions - as they say, "Publish or Perish".

          But don't let that disparage you ;)

          --
          Nadav Har'El | Saturday, Dec 2 2000, 5 Kislev 5761
          nyh@... |-----------------------------------------
          Phone: +972-53-245868, ICQ 13349191 |The 3 stages of sex: Tri-weekly, try
          http://nadav.harel.org.il |weekly, try weakly.
        • Shlomi Fish
          Revision 2 of the document is available on the site. Site URL: http://t2.technion.ac.il/~shlomif/graphs_equal/ Exact URL:
          Message 4 of 12 , Dec 2, 2000
          • 0 Attachment
            Revision 2 of the document is available on the site.

            Site URL: http://t2.technion.ac.il/~shlomif/graphs_equal/

            Exact URL:
            http://t2.technion.ac.il/~shlomif/graphs_equal/Docs/Description.txt

            Comments are welcome.

            Regards,

            Shlomi Fish



            ----------------------------------------------------------------------
            Shlomi Fish shlomif@...
            Home Page: http://t2.technion.ac.il/~shlomif/
            Home E-mail: shlomif@...

            The prefix "God Said" has the extraordinary logical property of
            converting any statement that follows it into a true one.
          Your message has been successfully submitted and would be delivered to recipients shortly.