Re: New algorithm for the isomorphism of graphs

4) Whereas even in the case of two graphs biparti, nonplanar. One can
always make a reduction for arrived obtained either from the trees or
of the planar ones.


This looks like it says that if you can find an algorithm for the case
of two trees, or the case of two planar graphs, then you can solve the
isomorphism problem in general. I seriously doubt that this is true,
since the Graph Isomorphism problem would be known to be in P.

Ok, if G is isomorphism with G' one can cut the graph of pieces, which
makes the algorithm, the vertices of G which of which in level I must
be isomorphism at the vertices of G' which are in level I. thus in the
case of the graphs biparti the algorithm crosses (I did not find
another word) in several graphs biparti...

Another thing, so in general one has two graphs G and G' isomorphisms,
and F the function of isomorphs and F (s) =s', one can obtained two
new graphs isomorphisms one removes s in G and s' in G'. And one can
the same operation for the edges: F (a,b) = a',b' and if one removes
in G the edge a, b (not the vertices a and b) and idem for G' the two
new graphs are always isomorphisms.

Then the problem of isomorphisms of the graphs biparti is reduced to
the problem planar graphs biparti, or trees and these two cases are
polynomial.

.

Relevant Pages

  • Re: New algorithm for the isomorphism of graphs
    ... of the planar ones. ... of two trees, or the case of two planar graphs, then you can solve the ... since the Graph Isomorphism problem would be known to be in P. ...
    (sci.math)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... On random input graphs graph isomorphism ... Note that testing degree sequences is a deterministic algorithm. ... The problem here is the algorithm relies on a hash function, ...
    (comp.theory)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... proved the graphs are not isomorphic. ... graphs are equal iff you have established an isomorphism between the two graphs, and to do that you have to cope with Bill Cox's automorphism issue. ...
    (sci.crypt)
  • Re: New algorithm for the isomorphism of graphs
    ... in bottom there are all the adjacent vertices at the vertex S. ... then the problem of the isomorphism of graphs is ... We want to explicitly construct an isomorphism F from G to ... neighbors of some candidate for F. ...
    (sci.math)
  • New algorithm for the isomorphism of graphs
    ... Here a method to find the function of isomorphism between two ... In the second graph there is a vertex which has the same pseudo-tree. ... then the problem of the isomorphism of graphs is ... one seeks in G' all the vertices which one dismantles equal ...
    (sci.math)